Preprint
Improved Approximation Algorithms for Geometric Set Cover
ArXiv.org
01/20/2005
DOI: 10.48550/arxiv.cs/0501045
Abstract
Given a collection S of subsets of some set U, and M a subset of U, the set
cover problem is to find the smallest subcollection C of S such that M is a
subset of the union of the sets in C. While the general problem is NP-hard to
solve, even approximately, here we consider some geometric special cases, where
usually U = R^d. Extending prior results, we show that approximation algorithms
with provable performance exist, under a certain general condition: that for a
random subset R of S and function f(), there is a decomposition of the portion
of U not covered by R into an expected f(|R|) regions, each region of a
particular simple form. We show that under this condition, a cover of size
O(f(|C|)) can be found. Our proof involves the generalization of shallow
cuttings to more general geometric situations. We obtain constant-factor
approximation algorithms for covering by unit cubes in R^3, for guarding a
one-dimensional terrain, and for covering by similar-sized fat triangles in
R^2. We also obtain improved approximation guarantees for fat triangles, of
arbitrary size, and for a class of fat objects.
Details
- Title: Subtitle
- Improved Approximation Algorithms for Geometric Set Cover
- Creators
- Kenneth L ClarksonKasturi Varadarajan
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.cs/0501045
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 01/20/2005
- Academic Unit
- Computer Science
- Record Identifier
- 9984411071502771
Metrics
3 Record Views