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 -