---
abstract: |
    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 ${\mathbb{R}}^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+{\varepsilon}$-approximation, $1+{\varepsilon}$-capacity violation) and arguably the first polynomial-time approximation algorithm for a non-trivial metric.
author:
- |
    Vincent Cohen-Addad\
    Sorbonne Université, CNRS, LIP6
bibliography:
- 'facilitylocationptas.bib'
title: Approximation Schemes for Capacitated Clustering in Doubling Metrics
---


