Conference proceeding
Weighted geometric set cover via quasi-uniform sampling
Proceedings of the forty-second ACM symposium on theory of computing, pp.641-648
STOC '10
06/05/2010
DOI: 10.1145/1806689.1806777
Abstract
There has been much progress on geometric set cover problems, but most known techniques only apply to the unweighted setting. For the weighted setting, very few results are known with approximation guarantees better than that for the combinatorial set cover problem. In this article, we employ the idea of quasi-uniform sampling to obtain improved approximation guarantees in the weighted setting for a large class of problems for which such guarantees were known in the unweighted case. As a consequence of this sampling method, we obtain new results on the fractional set cover packing problem.
Details
- Title: Subtitle
- Weighted geometric set cover via quasi-uniform sampling
- Creators
- Kasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the forty-second ACM symposium on theory of computing, pp.641-648
- Publisher
- ACM
- Series
- STOC '10
- DOI
- 10.1145/1806689.1806777
- ISSN
- 0737-8017
- Language
- English
- Date published
- 06/05/2010
- Academic Unit
- Computer Science
- Record Identifier
- 9984259414602771
Metrics
3 Record Views