Improved Bounds for Metric Capacitated Covering Problems

Abstract

In the Metric Capacitated Covering (MCC) problem, given a set of balls $\mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$, the goal is to find a minimum sized subset ${\mathcal{B}}^{\prime }\subseteq \mathcal{B}$ and an assignment of the points in $P$ to the balls in ${\mathcal{B}}^{\prime }$ 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 $\beta <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$.

arXiv commentTo appear at European Symposia on Algorithms 2020