Constant-Factor Approximation for Capacitated Clustering in Low Dimension with $(1+\epsilon )k$ Centers

Abstract

In many applications of $k$-median and $k$-means, including load balancing and redistricting, each center can serve only a bounded number of clients. This leads to capacitated clustering, in which a client may be forced to use a distant center because all nearby ones are full. This loss of locality defeats the techniques behind approximation schemes, and no constant-factor approximation is known in general metrics even for capacitated $k$-median. A long line of work therefore opens $K=k+\lfloor \epsilon k\rfloor$ centers for a fixed $\epsilon \in (0,1]$, while respecting the capacities exactly. We give a deterministic polynomial-time algorithm for uniform soft capacities in low dimension, that is, when the clients or the center locations have bounded doubling dimension. With $K$ centers, its ratio is $3-2\epsilon$ for $k$-median and $9-8\epsilon$ for $k$-means, or $5-4\epsilon$ in ${\mathbb{R}}^d$. Apart from $k$-median in the plane, these are the first polynomial-time ratios bounded by a constant independent of $\epsilon$; previously, the best ratio was $O({\epsilon }^{-2}\log (1/\epsilon ))$, even for $k$-median. We also obtain ratios that stay bounded as $\epsilon \to 0$ for non-uniform and hard capacities in low dimension, and ratios polylogarithmic in $1/\epsilon$ in general metrics. Our approach starts from a simple structural observation: a near-optimal uncapacitated solution can be split into fewer than $2k$ capacity-respecting blocks, so $2k$ centers already suffice, one per block. Our main tool, the rescue lemma, shows that once every block that sends clients to a center of the optimal solution is rescued (given a private center), that center can be closed, so each extra center effectively rescues about two blocks. This lets $\lfloor \epsilon k\rfloor$ extra centers rescue nearly an $\epsilon$-fraction of the blocks, yielding the linear dependence on $\epsilon$ in our ratios.