Journal of Computational Geometry jocg.org A CONSTANT-FACTOR APPROXIMATION FOR MULTI-COVERING WITH DISKS∗

Abstract. We consider 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 → 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 ∈ 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.