In this paper, we propose a fine-grained grid-based multi-objective model which aims at optimizing base station antennas' configurations, such as transmit power, antenna tilt and antenna azimuth, in order to upgra...In this paper, we propose a fine-grained grid-based multi-objective model which aims at optimizing base station antennas' configurations, such as transmit power, antenna tilt and antenna azimuth, in order to upgrading network performance in cellular networks. As the model is non-convex, non-smooth and discrete and computationally expensive, we use decomposition method to solve the MOP problem. We mainly focus on addressing the scalarized sub-problem after decomposition. For the scalarized sub-problem, we propose an enhanced difference method. First, difference of each component is calculated, which provides the guidance of optimization. Then an OPSO is applied to search the optimal step length. The method is applied to GSM network optimization on an area in Beijing. The effect of the application shows that proposed method has a good performance, and is effective/efficient to solve mobile network optimization problems.展开更多
In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS n...In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS networks restrict the number of paths that a commodity can use, for maintaining the quality of service (QoS) of the users, the demand of each commodity must be satisfied. Under the above conditions, some links in the network may be too much loaded, affecting the performance of the whole network drastically. For this problem, in [1], we proposed two mathematical models to describe it and a heuristic algorithm which quickly finds transmitting paths for each commodity are also presented. In this paper, we propose a new heuristic algorithm which finds a feasible path set for each commodity, and then select some paths from the path set through a mixed integer linear programming to transmit the demand of each commodity. This strategy reduces the scale of the original problem to a large extent. We test 50 instances and the results show the effectiveness of the new heuristic algorithm.展开更多
In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular funct...In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.展开更多
The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular(BP)functions with partial monotonicity under a streaming fashion.In this model,elements are randomly released from the s...The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular(BP)functions with partial monotonicity under a streaming fashion.In this model,elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions.The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible.In this work,a threshold-based streaming algorithm is presented for the BP maximization that attains a(1-k)/(2-k)-O(e)-approximation with O(1/e^(4)1og^(3)(1/s)log(2-k)k/(1-k)^(2))memory complexity,where k denotes the parameter of supermodularity ratio.We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation.We finally investigate this fair model under the streaming fashion and provide a(1-k)^(4)/(2-2k+k^(2))^(2)-O(e)-approximation algorithm.展开更多
文摘In this paper, we propose a fine-grained grid-based multi-objective model which aims at optimizing base station antennas' configurations, such as transmit power, antenna tilt and antenna azimuth, in order to upgrading network performance in cellular networks. As the model is non-convex, non-smooth and discrete and computationally expensive, we use decomposition method to solve the MOP problem. We mainly focus on addressing the scalarized sub-problem after decomposition. For the scalarized sub-problem, we propose an enhanced difference method. First, difference of each component is calculated, which provides the guidance of optimization. Then an OPSO is applied to search the optimal step length. The method is applied to GSM network optimization on an area in Beijing. The effect of the application shows that proposed method has a good performance, and is effective/efficient to solve mobile network optimization problems.
文摘In the multiple protocol label-switched (MPLS) networks, the commodities are transmitted by the label-switched paths (LSPs). For the sake of reducing the total cost and strengthening the central management, the MPLS networks restrict the number of paths that a commodity can use, for maintaining the quality of service (QoS) of the users, the demand of each commodity must be satisfied. Under the above conditions, some links in the network may be too much loaded, affecting the performance of the whole network drastically. For this problem, in [1], we proposed two mathematical models to describe it and a heuristic algorithm which quickly finds transmitting paths for each commodity are also presented. In this paper, we propose a new heuristic algorithm which finds a feasible path set for each commodity, and then select some paths from the path set through a mixed integer linear programming to transmit the demand of each commodity. This strategy reduces the scale of the original problem to a large extent. We test 50 instances and the results show the effectiveness of the new heuristic algorithm.
基金This work was supported by the Beijing Natural Science Foundation Project(No.Z220004)the National Natural Science Foundation of China(Nos.11901544 and 12101587)the China Postdoctoral Science Foundation(No.2022M720329).
文摘In this work,we study a k-Cardinality Constrained Regularized Submodular Maximization(k-CCRSM)problem,in which the objective utility is expressed as the difference between a non-negative submodular and a modular function.No multiplicative approximation algorithm exists for the regularized model,and most works have focused on designing weak approximation algorithms for this problem.In this study,we consider the k-CCRSM problem in a streaming fashion,wherein the elements are assumed to be visited individually and cannot be entirely stored in memory.We propose two multipass streaming algorithms with theoretical guarantees for the above problem,wherein submodular terms are monotonic and nonmonotonic.
基金supported by the National Natural Science Foundation of China(No.12101587)the China Postdoctoral Science Foundation(No.2022M720329)+2 种基金the National Natural Science Foundation of China(No.12001523)the Beijing Natural Science Foundation Project(No.Z200002)the National Natural Science Foundation of China(No.12131003).
文摘The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular(BP)functions with partial monotonicity under a streaming fashion.In this model,elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions.The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible.In this work,a threshold-based streaming algorithm is presented for the BP maximization that attains a(1-k)/(2-k)-O(e)-approximation with O(1/e^(4)1og^(3)(1/s)log(2-k)k/(1-k)^(2))memory complexity,where k denotes the parameter of supermodularity ratio.We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation.We finally investigate this fair model under the streaming fashion and provide a(1-k)^(4)/(2-2k+k^(2))^(2)-O(e)-approximation algorithm.