Approximation Schemes for Capacitated Clustering in Doubling Metrics

We consider the classic uniform capacitated k-median and uniform capacitated k-means problems in bounded doubling metrics. We provide the first QPTAS for both problems and the first PTAS for the k-median version for points in ℝ2. This is the first improvement over the bicriteria QPTAS for capacitated k-median in low-dimensional Euclidean space of Arora, Raghavan, Rao [STOC 1998] (1 + ε-approximation, 1 + ε-capacity violation) and arguably the first polynomial-time approximation algorithm for a non-trivial metric. Our result relies on a new structural proposition that applies to any metric space and that may be of interest for developping approximation algorithms for the problem in other metric spaces, such as for example planar or minor-free metrics.