A note on multicovering with disks

In the Disk Multicover problem the input consists of a set P of n points   in the plane, where each point p∈Pp∈P has a covering requirement k(p)k(p), and a set B of m base stations  , where each base station b∈Bb∈B has a weight w(b)w(b). If a base station b∈Bb∈B is assigned a radius r(b)r(b), it covers   all points in the disk of radius r(b)r(b) centered at b  . The weight of a radii assignment r:B→Rr:B→R is defined as ∑b∈Bw(b)r(b)α∑b∈Bw(b)r(b)α, for some constant α. A feasible solution is an assignment such that each point p   is covered by at least k(p)k(p) disks, and the goal is to find a minimum weight feasible solution. The Polygon Disk Multicover problem is a closely related problem, in which the set P is a polygon (possibly with holes), and the goal is to find a minimum weight radius assignment that covers each point in P at least K   times. We present a 3αkmax3αkmax-approximation algorithm for Disk Multicover, where kmaxkmax is the maximum covering requirement of a point, and a (3αK+ε)(3αK+ε)-approximation algorithm for Polygon Disk Multicover.