A constant-factor approximation for multi-covering with disks
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, a coverage function $\kappa :X \rightarrow \mathbb{N}$, and a constant $\alpha \geq 1$. Centered at each server is a single disk whose radius we are free...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2015-08-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/172 |
| Summary: | 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, a coverage function $\kappa :X \rightarrow \mathbb{N}$, and a constant $\alpha \geq 1$. Centered at each server is a single disk whose radius we are free to set. The requirement is that each client $x \in X$ be covered by at least $\kappa(x)$ of the server disks. The objective function we wish to minimize is the sum of the $\alpha$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.<br /><br /> |
|---|---|
| ISSN: | 1920-180X |