NeFut Logo NeFut
中 Admin Login

[CS.DS] Coresets for Capacitated Clustering via Dual Concentration

Published at: 2026-11-09 22:00 Last updated: 2026-11-12 00:51
#algorithm #AI #optimization

We investigate coresets for clustering, focusing on the classic $k$-median and $k$-means objectives. A coreset is a small weighted summary of the input that approximately preserves the clustering cost for any set of centers, serving as a key technique for scaling clustering algorithms to massive datasets. This paper addresses the capacitated setting, where cluster-size constraints must be respected alongside center selection. While this model naturally extends standard clustering and has been widely studied, its coreset complexity remains less understood. For finite metric spaces we obtain optimal‑size coresets that surprisingly match the best known bounds for unconstrained clustering. In Euclidean space we improve the bounds, presenting the first coresets with near‑linear dependence on $k$ that are independent of dimension and input size. The main technical contribution is concentration bounds for the dual solutions of min‑cost flow problems, enabling a simpler and tighter analysis of the sampling distribution used in the coreset construction.$$\text{size}=\tilde O\big(k\,\epsilon^{-2}\big)$$ where $\epsilon$ denotes the approximation error.\n\nReview: This work delivers a significant advance in the theory of coresets for capacitated clustering, offering optimal results for finite metrics and near‑linear $k$ dependence in Euclidean space, thus providing a practical tool for large‑scale constrained clustering.

Original Source: https://arxiv.org/abs/2611.09600

[h] Back to Home