On capacitated covering with unit balls

Abstract

In this paper, we consider the problem of capacitated covering with unit balls. In this problem, a set of weighted points in a metric space $({\mathrm{\Re }}^d,\rho )$ is given, and we want to cover them with a minimum number of the unit balls of that metric space provided that the total weight assigned to each unit ball is at most one. The problem is NP-hard as it generalizes the covering-with-unit-balls problem. We consider the problem in two cases: (1) the weight of each point can be split among several unit balls and (2) the unsplittable case. In the latter case, the problem is a generalization of the bin-packing problem even when $d=1$, and thus it is not approximable under 1.5, unless P=NP. We design a polynomial-time approximation scheme (PTAS) for the splittable case when $d$ is a fixed constant and $\rho$ is an ${\ell }_{\mathrm{p}}$ metric. This also results in a PTAS for the unsplittable case when all the points have the same weight. We also analyse several natural algorithms for this problem and prove that they achieve constant approximation factors.

Keywords:

• capacitated covering
• geometric covering
• constant-factor approximation
• computational geometry
• bin packing

Acknowledgement

We thank referees for their helpful comments, which improved the paper structure and content. We are grateful to an anonymous referee of one of our papers who gave us the basic idea of the combine algorithm. The authors also thank ‘Institute for Research in Fundamental sciences’ (IPM) for their support of this project. This research was in part supported by a grant from IPM. (No. CS1391-4-16).