In the capacitated $(k,z)$-clustering problem we must open $k$ centers and assign every client to a center while respecting each center’s capacity, minimizing the sum of the $z$‑th powers of the distances. $k$‑median corresponds to $z=1$ and $k$‑means to $z=2$.
We study polynomial‑time algorithms that are allowed to open $k+\lfloor\varepsilon k\rfloor$ centers and still satisfy the capacities exactly. All approximation ratios hold up to an additive $\delta$ for any fixed $\delta>0$.
For uniform soft capacities in low‑dimensional settings we achieve a ratio of $\beta-(\beta-1)\varepsilon$, where $\beta=3^{z}$ if either the clients or the locations have bounded doubling dimension, and $\beta=\mathcal{B}_z$ when only the clients have bounded doubling dimension while centers may lie anywhere in $\mathbb{R}^d$. Consequently we obtain $3-2\varepsilon$ for $k$‑median and $5-4\varepsilon$ for Euclidean $k$‑means. For hard capacities we still obtain a constant‑factor ratio, and for non‑uniform soft capacities we get $1+(3^{z}-1)e^{-\varepsilon}$. These are the first polynomial‑time constant‑factor guarantees that use only $(1+\varepsilon)k$ centers, apart from the planar uniform $k$‑median case.
In general metrics for uniform $k$‑median we improve the ratios to $3+2\ln(1/\varepsilon)$ for soft capacities and $7+2\ln(1/\varepsilon)$ for hard capacities, beating the previous $O(\varepsilon^{-2}\log(1/\varepsilon))$ bounds. The core idea is to split a near‑optimal uncapacitated solution into groups of at most $U$ clients (where $U$ is the capacity), yielding fewer than $2k$ groups. When fewer centers are available, groups must share centers. Each extra center can provide private centers to roughly two groups, because an optimal center that serves only such groups can be closed, thereby eliminating almost an $\varepsilon$‑fraction of the extra sharing cost.
Review: Overall, the paper delivers a significant breakthrough in capacitated clustering by achieving constant‑factor approximations with only a modest increase in the number of centers, offering a more practical algorithmic framework for capacity‑constrained applications.