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?P p ? P has a covering requirement k(p) k ( p ) , and a set B of m base stations , where each base station b?B b ? B has a weight w(b) w ( b ) . If a base station b?B b ? 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?R r : B ? R is defined as ?b?Bw(b)r(b)? ? b ? B w ( 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?kmax 3 ? k max -approximation algorithm for Disk Multicover, where kmax k max is the maximum covering requirement of a point, and a (3?K+?) ( 3 ? K + ? ) -approximation algorithm for Polygon Disk Multicover.
multicovering approximation algorithms disk cover