TY - GEN
T1 - On the set multi-cover problem in geometric settings
AU - Chekuri, Chandra
AU - Clarkson, Kenneth L.
AU - Sariel, Har Peled
PY - 2009
Y1 - 2009
N2 - We consider the set multi-cover problem in geometric settings. Givena set of points P and a collection of geometric shapes (or sets) ℱ, we wish to find a minimum cardinality subset of ℱ 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 paper, we show that similar improvements can be obtained for the multi-cover 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 multi-cover problem in geometric settings. Givena set of points P and a collection of geometric shapes (or sets) ℱ, we wish to find a minimum cardinality subset of ℱ 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 paper, we show that similar improvements can be obtained for the multi-cover 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.
KW - Cuttings
KW - LP rounding
KW - Set cover
UR - http://www.scopus.com/inward/record.url?scp=70849136362&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70849136362&partnerID=8YFLogxK
U2 - 10.1145/1542362.1542421
DO - 10.1145/1542362.1542421
M3 - Conference contribution
AN - SCOPUS:70849136362
SN - 9781605585017
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 341
EP - 350
BT - Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09
T2 - 25th Annual Symposium on Computational Geometry, SCG'09
Y2 - 8 June 2009 through 10 June 2009
ER -