Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
- 作者：Paz Carmi ; Matthew J. Katz ; Nissan Lev-Tov
- 关键词：Geometric optimization ; Approximation algorithms ; Discrete piercing ; Covering ; Wireless networks
- 刊名：Computational Geometry
- 出版年：2008
- 期刊代码：18_09257721
- 类别：cp
- 出版时间：April 2008
- 卷：39
- 期：3
- 页码：209-218
- 文件大小：262 K
摘要
Let 
be a set of disks of arbitrary radii in the plane, and let 
be a set of points. We study the following three problems: (i) Assuming 
contains the set of center points of disks in 
, find a minimum-cardinality subset 
of 
(if exists), such that each disk in 
is pierced by at least h points of 
, where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming 
is such that for each 
there exists a point in 
whose distance from D's center is at most αr(D), where r(D) is D's radius and 0
α<1 is a given constant, find a minimum-cardinality subset 
of 
, such that each disk in 
is pierced by at least one point of d024ca9">
. We call this problem minimum discrete piercing with cores. (iii) Assuming 
is the set of center points of disks in 13d25277027d60">
, and that each 
covers at most l points of 
, where l is a constant, find a minimum-cardinality subset 
of 
, such that each point of 
is covered by at least one disk of 
. We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary d025c5">
).
α<1 is a given constant, find a minimum-cardinality subset