Conference proceeding
Improved approximation algorithms for geometric set cover
Proceedings of the twenty-first annual symposium on computational geometry, pp.135-141
SCG '05
06/06/2005
DOI: 10.1145/1064092.1064115
Abstract
Given a collection S of subsets of some set U, and M ⊂ U, the set cover problem is to find the smallest subcollection C ⊂ 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 . Combining previously known techniques [3, 4], we show that polynomial time approximation algorithms with provable performance exist, under a certain general condition: that for a random subset R ⊂ S and function f(), there is a decomposition of the complement U ∖ ∪ Y ∈ R Y into an expected f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|)) can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudodisks, by a family of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects, and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in R 3 , and for guarding an x-monotone polygonal chain.
Details
- Title: Subtitle
- Improved approximation algorithms for geometric set cover
- Creators
- Kenneth Clarkson - BellKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the twenty-first annual symposium on computational geometry, pp.135-141
- Publisher
- ACM
- Series
- SCG '05
- DOI
- 10.1145/1064092.1064115
- Language
- English
- Date published
- 06/06/2005
- Academic Unit
- Computer Science
- Record Identifier
- 9984259432502771
Metrics
3 Record Views