In a sweep cover problem, positions of interest (PoIs) are required to be visited periodically by mobile sensors. In this paper, we propose a new sweep cover problem: the prize -collecting sweep cover problem (PCSC), ...
详细信息
In a sweep cover problem, positions of interest (PoIs) are required to be visited periodically by mobile sensors. In this paper, we propose a new sweep cover problem: the prize -collecting sweep cover problem (PCSC), in which penalty is incurred by those PoIs which are not sweep-covered, and the goal is to minimize the covering cost plus the penalty. Assuming that every mobile sensor has to be linked to some base station, and the number of base stations is upper bounded by a constant, we present a 5-LMP (Lagrangian Multiplier Preserving) algorithm. As a step stone, we propose the prize-collecting forest with k components problem (PCFk), which might be interesting in its own sense, and presented a 2-LMP for rooted PCFk. (C) 2022 Elsevier B.V. All rights reserved.
Given a graph G, the minimum Connected-k-Subgraph Cover problem (MinCkSC) is to find a minimum vertex subset C of G such that every connected subgraph of G on k vertices has at least one vertex in C. If furthermore th...
详细信息
Given a graph G, the minimum Connected-k-Subgraph Cover problem (MinCkSC) is to find a minimum vertex subset C of G such that every connected subgraph of G on k vertices has at least one vertex in C. If furthermore the subgraph of G induced by C is connected, then the problem is denoted as MinCkSC(con). In this paper, we first present a PTAS for MinCkSC on an H-minor-free graph, where H is a graph with a constant number of vertices. Then, we design an O((omega + 1)(2(k - 1)(omega + 2))(3 omega +3))|V|-time FPT algorithm for MinCkSC(con) on a graph with treewidth omega, based on which we further design an O(2(O(root tlog t)|V|O(1))) time subexponential FPT algorithm for MinCkSC(con) on an H-minor-free graph, where t is an upper bound of solution size.
Facility location problem is one of the most classical NP-hard problems in combinatorial optimization. In the metric facility location problem (MFLP), we are given a set of facilities, a set of clients and the metric ...
详细信息
Facility location problem is one of the most classical NP-hard problems in combinatorial optimization. In the metric facility location problem (MFLP), we are given a set of facilities, a set of clients and the metric distances between facilities and clients. In this paper, we consider the squared metric facility location problem (SMFLP) with nonuniform capacities, where each facility has a nonuniform capacity to serve a limited amount of client demands, and the distances between facilities and clients are no longer metric but squared metric. Fernandes et al. (2015) analyze the LP-based algorithms for the MFLP when they are applied to the SMFLP and achieve constant approximation ratios. In this paper, we do the same thing on local search algorithm, one of the most powerful techniques for MFLP with nonuniform capacities. Particularly, we propose the first constant approximation algorithm with approximation ratio 13 + epsilon for the SMFLP with nonuniform capacities. (C) 2019 Elsevier B.V. All rights reserved.
This paper presents a three-dimensional (3D) massive multiple-input and multiple-output (MIMO) antenna array model, which includes the spherical array assumption and geometric properties for future fifth generation (5...
详细信息
This paper presents a three-dimensional (3D) massive multiple-input and multiple-output (MIMO) antenna array model, which includes the spherical array assumption and geometric properties for future fifth generation (5G) wireless communications. A parametric approximation algorithm is developed for estimating the spatial fading correlations (SFCs) and channel capacities of the 3D massive MIMO antenna array systems under different power angular spectrum (PAS). The relationship between correlation with the spacing of antenna arrays and angular parameters was classified. The results show that the simulation values of the approximate method fit the theoretical calculation very well, thereby validating the feasibility of the proposed 3D large-scale massive MIMO model.
The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at ...
详细信息
The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0-1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+I mu for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756-765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424-436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.
Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element s...
详细信息
Partial set cover problem and set multi-cover problem are two generalizations of the set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set E, a collection of sets S subset of 2(E), a total covering ratio q, each set S is an element of S is associated with a cost c(S), each element e is an element of E is associated with a covering requirement re, the goal is to find a minimum cost sub-collection S' subset of S to fully cover at least q vertical bar E vertical bar elements, where element e is fully covered if it belongs to at least r(e) sets of S'. Denote by r(max) = max{r(e) : e is an element of E} the maximum covering requirement. We present an (O(r(max) log(2) n(1+ ln(1/epsilon) + 1-q/epsilon q)), 1 - epsilon)-bicriteria approximation algorithm, that is, the output of our algorithm has cost O(r(max) log(2) n(1+ ln(1/epsilon) + 1-q/epsilon q)) times of the optimal value while the number of fully covered elements is at least (1 - epsilon)q vertical bar E vertical bar.
We study a scenario-based stochastic and prize-collecting version of the set multicover problem, where there is uncertainty about a demand for each element to be covered and the penalty cost is imposed linearly on the...
详细信息
We study a scenario-based stochastic and prize-collecting version of the set multicover problem, where there is uncertainty about a demand for each element to be covered and the penalty cost is imposed linearly on the shortfall in each demand. This problem is NP-hard and has an application in shift scheduling in crowdsourced delivery services. For this problem, we present an LP-based O(ln n)-approximation algorithm, where n is the number of elements to be covered. (C) 2022 Elsevier B.V. All rights reserved.
We present a new polynomial-time heuristic algorithm for finding a solution to the Traveling Salesman Problem (TSP) for any complete and edge-weighted graph K sub(n), with a set of vertices V and a set of edges E wher...
详细信息
We present a new polynomial-time heuristic algorithm for finding a solution to the Traveling Salesman Problem (TSP) for any complete and edge-weighted graph K sub(n), with a set of vertices V and a set of edges E where !V! = n. In a few words, this method is based on the idea of linking the elements of V progressively, one by one, in such a way that the vertex selection which produces fewest disturbances to the other vertices not yet connected, will be selected as the next vertex to join to the subset of already connected vertices. When the cost of the result is compared to the cost of the best circuit, it appears that a good sub-solution is obtained in most of the cases tested. Moreover, comparison tests made between the heuristic introduced and the well-known Quick method, produce a better behaviour, for almost every case, in the first approach.
In this paper, we consider a variant of the classical uncapacitated facility location problem, so-called squared metric two-stage stochastic facility location problem (SM-2-SFLP) which can treat the uncertainty of the...
详细信息
In this paper, we consider a variant of the classical uncapacitated facility location problem, so-called squared metric two-stage stochastic facility location problem (SM-2-SFLP) which can treat the uncertainty of the set of clients and facility costs. We assume that the connection cost is squared metric, a variant of the metric case which is widely researched. We give a new 0-1 integer linear programming for SM-2-SFLP. Based on the new formulation, we apply two known algorithms to SM-2-SFLP, and analyze the approximation ratio and per-scenario bound respectively.
作者：
Liu, SudingYunnan Univ
Sch Math & Stat Kunming 650504 Peoples R China Univ Waterloo
David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada
We address the 1-line Steiner tree problem with minimum number of Steiner points. Given a line l, a point set P of n terminals in R-2 and a positive constant K, we are asked to find a Steiner tree T-l to interconnect ...
详细信息
We address the 1-line Steiner tree problem with minimum number of Steiner points. Given a line l, a point set P of n terminals in R-2 and a positive constant K, we are asked to find a Steiner tree T-l to interconnect the line l and the n terminals such that the Euclidean length of each edge in T-l is no more than the given positive constant K except those connecting two points on the line l, the objective is to minimize total number of the Steiner points in T-l, i.e. min T-l {vertical bar S-out vertical bar + vertical bar S-on vertical bar}, where vertical bar S-out vertical bar and vertical bar S-on vertical bar are the number of Steiner points located outside of the line l and on this line l, respectively. We design a 4-approximation algorithm with time complexity of O(n(3)) for the 1-line Steiner tree problem with minimum number of Steiner points.
暂无评论