Conference proceeding
A constant-factor approximation for multi-covering with disks
Proceedings of the twenty-ninth annual symposium on computational geometry, pp.243-248
SoCG '13
06/17/2013
DOI: 10.1145/2462356.2462400
Abstract
We consider variants of the following multi-covering problem with disks. We are given two point sets Y (servers) and X (clients) in the plane, and a coverage function κ :X -> N. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client x ∈ X be covered by at least κ(x) of the server disks. The objective function we wish to minimize is the sum of the areas of the disks. We present a polynomial time algorithm for this problem achieving an O(1) approximation.
Details
- Title: Subtitle
- A constant-factor approximation for multi-covering with disks
- Creators
- Santanu Bhowmick - University of IowaKasturi Varadarajan - University of IowaShi-Ke Xue - Massachusetts Institute of Technology
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the twenty-ninth annual symposium on computational geometry, pp.243-248
- Series
- SoCG '13
- DOI
- 10.1145/2462356.2462400
- Publisher
- ACM
- Language
- English
- Date published
- 06/17/2013
- Academic Unit
- Computer Science
- Record Identifier
- 9984259433602771
Metrics
24 Record Views