A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI ro...
详细信息
A special case of the bottleneck Steiner tree problem in the Euclidean plane was considered in this paper. The problem has applications in the design of wireless communication networks, multifacility location, VLSI routing and network routing. For the special case which requires that there should be no edge connecting any two Steiner points in the optimal solution, a 3-restricted Steiner tree can be found indicating the existence of the performance ratio root2. In this paper, the special case of the problem is proved to be NP-hard and cannot be approximated within ratio root2. First a simple polynomial time approximation algorithm with performance ratio root3 is presented. Then based on this algorithm and the existence of the 3-restricted Steiner tree, a polynomial time approximation algorithm with performance ratio-root2 + epsilon is proposed, for any epsilon > 0.
In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant virtual backbone ...
详细信息
In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant virtual backbone can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). In this paper, we present a constant approximation algorithm for the minimum weight (k, m)-CDS problem in unit disk graphs under the assumption that k and m are two fixed constants with m >= k. Prior to this paper, constant approximation algorithms are known for k = 1 with weight and 2 <= k <= 3 without weight. Our result is the first constant approximation algorithm for the (k, m)-CDS problem with general k, m and with weight. The performance ratio is (alpha+5 rho) for k >= 3 and (alpha+2.5 rho) for k = 2, where a is the performance ratio for the minimum weight m-fold dominating set problem and. is the performance ratio for the subset k-connected subgraph problem (both problems are known to have constant performance ratios).
作者：
Feng, WangsenZhang, Li'angWang, HanpinPeking Univ
Ctr Comp Minist Educ Key Lab Network & Software Secur Assurance Beijing 100871 Peoples R China Peking Univ
Sch Elect Engn & Comp Sci Minist Educ Key Lab High Confidence Software Technol Beijing 100871 Peoples R China
We propose a polynomial time approximation algorithm for a novel maximum edge coloring problem which arises from wireless mesh networks [Ashish Raniwala, Tzi-cker Chiueh, Architecture and algorithms for an IEEE 802.11...
详细信息
We propose a polynomial time approximation algorithm for a novel maximum edge coloring problem which arises from wireless mesh networks [Ashish Raniwala, Tzi-cker Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, in: INFOCOM 2005, pp. 2223-2234;Ashish Raniwala, Kartik Gopalan, Tzi-cker Chiueh, Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks, Mobile Comput. Commun. Rev. 8 (2) (2004) 50-65]. The problem is to color all the edges in a graph with maximum number of colors under the following q-Constraint: for every vertex in the graph, all the edges incident to it are colored with no more than q (q is an element of Z, q >= 2) colors. We show that the algorithm is a 2-approximation for the case q = 2 and a (1 + 4q-2/3q(2)-5q+2)-approximation for the case q > 2 respectively. The case q = 2 is of great importance in practice. For complete graphs and trees, polynomial time accurate algorithms are found for them when q = 2. The approximation algorithm gives a feasible solution to channel assignment in multi-channel wireless mesh networks. (C) 2008 Elsevier B.V. All rights reserved.
The k-means problem is a classical combinatorial optimization problem which has lots of applications in many fields such as machine learn-ing, data mining, etc. We consider a variant of k-means problem in the spherica...
详细信息
The k-means problem is a classical combinatorial optimization problem which has lots of applications in many fields such as machine learn-ing, data mining, etc. We consider a variant of k-means problem in the spherical space, that is, spherical k-means problem with penalties. In the problem, it is allowable that some nodes in the spherical space can not be clustered by paying some penalty costs. Based on local search scheme, we propose a (4(11 + 4 root 7) + epsilon)-approximation algorithm using singe-swap oper-ation, where E is a positive constant.
In a minimum partial set multi-cover problem (MinPSMC), given an element set X, a collection of subsets S subset of 2(X), a cost c(S) on each set S is an element of S, a covering requirement r(x) for each element x is...
详细信息
In a minimum partial set multi-cover problem (MinPSMC), given an element set X, a collection of subsets S subset of 2(X), a cost c(S) on each set S is an element of S, a covering requirement r(x) for each element x is an element of X, and an integer k, the goal is to find a sub-collection F subset of S to fully cover at least k elements such that the cost of F is as small as possible, where element x is fully covered by F if it belongs to at least r(x) sets of F. Recently, it was proved that MinPSMC is at least as hard as the densest k-subgraph problem. The question is: how about the problem in some geometric settings? In this paper, we consider the MinPSMC problem in which X is a set of points on the plane and S is a set of unit squares (MinPSMC-US). Under the assumption that r(x) = f(x) for every x is an element of X, where f(x) = vertical bar{S is an element of S : x is an element of S}vertical bar is the number of sets containing element x, we design an approximation algorithm achieving approximation ratio (1 + epsilon) for MinPSMC-US.
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.
暂无评论