# Approximation Schemes for Capacitated Clustering in Doubling Metrics

arXiv: https://arxiv.org/abs/1812.07721 · HTML: https://mlsanity.com/paper/1812.07721/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2018.

## Built on by (most cited first, 1 of 1)

- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)

## Abstract (arXiv)

Motivated by applications in redistricting, we consider the 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 uniform capacitated k-median problem for points in R2 . 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.