A PTAS for the cardinality constrained covering with unit balls

In this paper, we address the cardinality constrained covering with unit balls problem: given a positive integer L and a set of n   points in RdRd, partition them into a minimum number of parts such that each part contains at most L   points and it can be covered by a unit ball of the given ℓpℓp metric. Developing a constant-factor approximation algorithm for this problem is an old open problem. By proving a structural property in the problem and applying the shifting strategy and dynamic programming, we derive the first (1+ε)d(1+ε)d-approximation nO(1/εd)nO(1/εd)-time algorithm for this problem when d is a fixed constant.