在容量 $(k,z)$-聚类问题中，我们需要打开 $k$ 个中心，并在满足每个中心容量的前提下，将每个客户分配到某个中心，使得距离的 $z$ 次幂之和最小。$k$-median 对应 $z=1$，$k$-means 对应 $z=2$。
本文研究在多项式时间内打开 $k+\lfloor\varepsilon k\rfloor$ 个中心且严格遵守容量限制的算法。所有近似比在任意固定的 $\delta>0$ 下都可加上 $\delta$ 的容差。
对于低维空间中的均匀软容量，我们得到的近似比为 $\beta-(\beta-1)\varepsilon$，其中若客户或位置的倍增维数有界，则 $\beta=3^{z}$；若仅客户的倍增维数有界且中心可以任意放在 $\mathbb{R}^d$，则 $\beta=\mathcal{B}_z$。因此 $k$-median 的比率为 $3-2\varepsilon$，欧氏 $k$-means 为 $5-4\varepsilon$。对于硬容量，我们仍能得到常数因子的比率；对于非均匀软容量，得到 $1+(3^{z}-1)e^{-\varepsilon}$ 的比率。这是首批在仅使用 $(1+\varepsilon)k$ 个中心且比率保持常数的多项式时间算法，除平面上的均匀 $k$-median 外。
在一般度量空间的均匀 $k$-median 中，软容量下的比率为 $3+2\ln(1/\varepsilon)$，硬容量下为 $7+2\ln(1/\varepsilon)$，显著改进了之前的 $O(\varepsilon^{-2}\log(1/\varepsilon))$ 结果。关键思路是：先对一个接近最优的无容量限制解进行聚类划分，使每组至多包含 $U$（容量）个客户，可得到少于 $2k$ 个组。若中心数不足，则需要组之间共享中心。每增加一个额外中心，大约可以为两组提供私有中心，因为可以关闭只服务这些组的最优中心，从而消除约 $\varepsilon$ 比例的共享成本。
点评：总体来看，本文在容量聚类领域提供了在仅略增中心数量的情况下实现常数近似比的突破，为实际应用中的容量约束提供了更具可行性的算法框架。