Loading [MathJax]/extensions/tex2jax.js
Im­proved Bounds for Met­ric Ca­pac­i­tated Cov­er­ing Prob­lems
Sayan Bandya­pad­hyay
Uni­ver­sity of Bergen

In the Met­ric Ca­pac­i­tated Cov­er­ing (MCC) prob­lem, given a set of balls B in a met­ric space P with met­ric d and a ca­pac­ity pa­ra­me­ter U, the goal is to find a min­i­mum sized sub­set B' of B and an as­sign­ment of the points in P to the balls in B' such that each point is as­signed to a ball that con­tains it and each ball is as­signed with at most U points. MCC achieves an O(log |P|)-ap­prox­i­ma­tion using a greedy al­go­rithm. On the other hand, it is hard to ap­prox­i­mate within a fac­tor of o(log |P|) even with less than 3 fac­tor ex­pan­sion of the balls. Bandya­pad­hyay~{et al.} [SoCG 2018, DCG 2019] showed that one can ob­tain an O(1)-ap­prox­i­ma­tion for the prob­lem with 6.47 fac­tor ex­pan­sion of the balls. An open ques­tion left by their work is to re­duce the gap be­tween the lower bound 3 and the upper bound 6.47. In this cur­rent work, we show that it is pos­si­ble to ob­tain an O(1)-ap­prox­i­ma­tion with only 4.24 fac­tor ex­pan­sion of the balls. We also show a sim­i­lar upper bound of 5 for a more gen­er­al­ized ver­sion of MCC for which the best pre­vi­ously known bound was 9. (This work was pre­sented at ESA 2020.)