On the set multi-cover problem in geometric settings

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual Symposium on Computational Geometry, SCG'09
Pages341-350
Number of pages10
DOIs
StatePublished - Dec 4 2009
Event25th Annual Symposium on Computational Geometry, SCG'09 - Aarhus, Denmark
Duration: Jun 8 2009Jun 10 2009

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other25th Annual Symposium on Computational Geometry, SCG'09
Country/TerritoryDenmark
CityAarhus
Period6/8/096/10/09

Keywords

  • Cuttings
  • LP rounding
  • Set cover

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'On the set multi-cover problem in geometric settings'. Together they form a unique fingerprint.

Cite this