On the Set Multi-Cover Problem in Geometric Settings

Chandra Chekuri,
Kenneth L. Clarkson,
and Sariel Har-Peled

We consider the set multi-cover 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 in P is
covered(contained in) at least demand(p) sets. Here
demand(p) is an integer demand (requirement) for
p. When the demands demand(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 Vpt) 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.
PDF
Last modified: Fri Mar 6 16:04:12 CST 2009