Capacitated Clustering with Few Extra Centers

Abstract

In capacitated $(k,z)$-clustering, we open $k$ centers and assign every client to a center within its capacity, minimizing the sum of $z$-th powers of the distances; $k$-median and $k$-means are the cases $z=1$ and $z=2$. We study polynomial-time algorithms that open $k+\lfloor \epsilon k\rfloor$ centers but respect the capacities exactly. All ratios hold up to an additive $\delta$ for every fixed $\delta >0$. For uniform soft capacities in low dimensions, we obtain ratio $\beta -(\beta -1)\epsilon$, where $\beta =3^z$ if the clients or the locations have bounded doubling dimension, and $\beta ={\mathcal{B}}_z<3^z$ for $z>1$ if the clients do and centers may lie anywhere in ${\mathbb{R}}^d$. This gives $3-2\epsilon$ for $k$-median and $5-4\epsilon$ for Euclidean $k$-means. We also obtain ratios bounded by a constant for hard capacities, and $1+(3^z-1)e^{-\epsilon }$ for non-uniform soft capacities. These are the first polynomial-time ratios with $(1+\epsilon )k$ centers that are bounded by a constant, apart from uniform $k$-median in the plane. For uniform $k$-median in general metrics, we obtain $3+2\ln (1/\epsilon )$ with soft and $7+2\ln (1/\epsilon )$ with hard capacities, improving the previous $O({\epsilon }^{-2}\log (1/\epsilon ))$. Splitting the clusters of a near-optimal uncapacitated solution into groups of at most $U$ clients, where $U$ is the capacity, gives fewer than $2k$ groups. With fewer centers, groups must share centers. Each extra center gives private centers to about two groups, since a center of an optimal solution that serves only such groups can be closed. Thus $\lfloor \epsilon k\rfloor$ extra centers remove almost an $\epsilon$-fraction of the extra cost caused by sharing.