A constant-factor approximation for multi-covering with disks - Santanu Bhowmick; Kasturi Varadarajan; Shi-Ke Xue (Journal of Computational Geometry, 2015)
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 $κ :X → \mathbb{N}$, and a constant $α ≥ 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 $κ(x)$ of the server disks. The objective function we wish to minimize is the sum of the $α$-th powers of the disk radii. We present a polynomial time algorithm for this problem achieving an $O(1)$ approximation.