On the Set Multi-Cover Problem in Geometric Settings

Details On the Set Multi-Cover Problem in Geometric Settings On the Set Multi-Cover Problem in Geometric Settings

2009-09-02

arxiv.org/abs/0909.0537v1

Computer Science

Computational Geometry

Scientific paper

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 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, where Opt is the cardinality of an optimal solution, and an O(1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes.

Affiliated with

Also associated with

No associations

Rating

On the Set Multi-Cover Problem in Geometric Settings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Set Multi-Cover Problem in Geometric Settings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Set Multi-Cover Problem in Geometric Settings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-663280