On capacitated covering with unit balls
Taha Ghasemi, Mohammadreza Razzazi · International Journal of Computer Mathematics · 2014
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 (ℜd,ρ) 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 ρ is an ℓ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.