Improved Bounds for Metric Capacitated Covering Problems
Sayan Bandyapadhyay
University of Bergen

In the Metric Capacitated Covering (MCC) problem, given a set of balls B in a metric space P with metric d and a capacity parameter U, the goal is to find a minimum sized subset B' of B and an assignment of the points in P to the balls in B' such that each point is assigned to a ball that contains it and each ball is assigned with at most U points. MCC achieves an O(log |P|)-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of o(log |P|) even with less than 3 factor expansion of the balls. Bandyapadhyay~{et al.} [SoCG 2018, DCG 2019] showed that one can obtain an O(1)-approximation for the problem with 6.47 factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound 3 and the upper bound 6.47. In this current work, we show that it is possible to obtain an O(1)-approximation with only 4.24 factor expansion of the balls. We also show a similar upper bound of 5 for a more generalized version of MCC for which the best previously known bound was 9. (This work was presented at ESA 2020.)