TY - JOUR
T1 - On the set multicover problem in geometric settings
AU - Chekuri, Chandra
AU - Clarkson, Kenneth L.
AU - Har-Peled, Sariel
PY - 2012/12
Y1 - 2012/12
N2 - We consider the set multicover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subset of F such that each point p ∈ P is covered by (contained in) at least d(p) sets. Here, d(p) is an integer demand (requirement) for p. When the demands d(p) = 1 for all p, this is the standard set cover problem. The set cover problem in geometric settings admits an approximation ratio that is better than that for the general version. In this article, we show that similar improvements can be obtained for the multicover problem as well. In particular, we obtain an O(log opt) approximation for set systems of bounded VC-dimension, and an O(1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes.
AB - We consider the set multicover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subset of F such that each point p ∈ P is covered by (contained in) at least d(p) sets. Here, d(p) is an integer demand (requirement) for p. When the demands d(p) = 1 for all p, this is the standard set cover problem. The set cover problem in geometric settings admits an approximation ratio that is better than that for the general version. In this article, we show that similar improvements can be obtained for the multicover problem as well. In particular, we obtain an O(log opt) approximation for set systems of bounded VC-dimension, and an O(1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes.
UR - http://www.scopus.com/inward/record.url?scp=84872482196&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872482196&partnerID=8YFLogxK
U2 - 10.1145/2390176.2390185
DO - 10.1145/2390176.2390185
M3 - Article
AN - SCOPUS:84872482196
SN - 1549-6325
VL - 9
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 1
M1 - 9
ER -