Coresets for Capacitated Clustering via Dual Concentration

Milind Prabhu; Chris Schwiegelshohn; Sudarshan Shyam; Erik Waingarten

cs.DSNov 6, 2026

Coresets for Capacitated Clustering via Dual Concentration

Authors: Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam, Erik Waingarten

Abstract

We study coresets for clustering problems, focusing on the classical $k$ -median and $k$ -means objectives. A coreset is a small weighted summary of the input data that approximately preserves the clustering cost for every choice of centers. Such summaries are a central tool for scaling clustering algorithms to large datasets. In this work, we consider the capacitated setting, where the clustering is subject not only to choosing centers but also to respecting prescribed cluster-size constraints. This model is a natural generalization of standard clustering and has been widely studied, but its coreset complexity is less well understood. For finite metric spaces, we obtain optimal-size coresets; surprisingly, these match the best-known bounds for unconstrained clustering. We also give improved coreset bounds in Euclidean space, notably the first coresets with near-linear dependence in $k$ while being independent of the dimension and input size. The main new technical ingredients are concentration bounds for the dual solutions of min-cost flow problems, which allow for both significantly simpler and tighter analyses of the underlying sampling distribution used in the coreset construction.

Figures & tables

Reference	Coreset Size $(k\text{-median},k\text{-means})$
Cohen-Addad, Li [ 14 ]	$\tilde{O}(k^{2}\varepsilon^{-5}\log^{2}n)$
Cohen-Addad, Li [ 14 ]	$\tilde{O}(k^{5}\varepsilon^{-5}\log^{5}n)$
Schmidt, Schwiegelshohn, Sohler [ 38 ]	$O(k\varepsilon^{-d-1}\log n)$
Schmidt, Schwiegelshohn, Sohler [ 38 ]	$O(k\varepsilon^{-d-2}\log n)$
Huang, Jiang, Vishnoi [ 28 ]	$O(k^{2}\varepsilon^{-d})$
Huang, Jiang, Vishnoi [ 28 ]	$O(k^{3}\varepsilon^{-d-1})$

Table 1: Coreset size bounds for cardinality-constrained clustering in

d

-dimensional Euclidean space. For each reference, the first bound is for

k

-median and the second is for

k

-means.

T=\Theta\left(\frac{k\log N+\log(1/\delta)}{\varepsilon^{2}}\right).

Algorithm 1 Product Ring Sampling for Finite-Metric Capacitated

k\text{-}\mathrm{median}

\pi_{j}(p)=\frac{1}{2}\left(\frac{1}{|P_{j}|}+\frac{r_{p}}{\Phi_{j}}\right),\qquad p\in P_{j}.

Algorithm 2 Mass-preserving sensitivity sampling for Euclidean capacitated

k\text{-}\mathrm{median}

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 361 papers

Beyond Worst-Case Coreset Bounds for $k$ -Clustering via Determinantal Sampling
Sep 6, 2026Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar +1Coreset Selection Clustering
School of Computing, National University of Singapore · Department of Mathematics, National University of Singapore · Department of Mathematics, Indian Institute of Technology Bombay
EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset
Aug 17, 2026Haoyun Yin, Chuanhui Liu, Xiao WangCoreset Selection Optimal Transport
Department of Statistics, Purdue University West Lafayette, IN 47906, USA
Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
Apr 17, 2026Nicole Funk, Annika Hennes, Johanna Hillebrand +1Clustering Group Fairness
Department of Informatics, University of Cologne, Germany · Heinrich Heine University Düsseldorf, Faculty of Mathematics and Natural Sciences, Germany · Department of Informatics, University of Bonn, Germany

Sep 6, 2026J/K move · Enter open · S save

Beyond Worst-Case Coreset Bounds for $k$ -Clustering via Determinantal Sampling

Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar, Hoang-Son Tran

School of Computing, National University of Singapore · Department of Mathematics, National University of Singapore · Department of Mathematics, Indian Institute of Technology Bombay

Coreset Selection Clustering

Open paper AskPDF arXiv

Massive datasets in modern machine learning have made data reduction a central challenge, particularly for clustering tasks where memory and computational constraints demand compact yet faithful summaries. A standard approach is to construct an \textit{

ε

-coreset}: a small weighted subset that approximately preserves the clustering cost for every plausible choice of centers. For the \textit{

(k,z)

-clustering problem}, existing worst-case bounds on coreset size are essentially tight, ruling out substantially smaller coresets in general. However, such worst-case instances are often unrepresentative of real-world data. In this work, we show that significantly smaller coresets are possible under mild and natural assumptions on the underlying data distribution. We introduce a new correlated sampling framework, called determinantal sampling, based on a novel application of determinantal point processes. Using this framework, we obtain an efficiently constructible

\varepsilon

-coreset for

(k,z)

-clustering in

\mathbb R^d

whose dependence on

1/\varepsilon

has exponent strictly smaller than

2

when

d

is fixed. This improves over the worst-case

\varepsilon^{-2}

barrier under our beyond-worst-case assumptions. To the best of our knowledge, this is the first result that provably surpasses these lower bounds through beyond-worst-case assumptions. Finally, we validate our approach on synthetic and real-world benchmark datasets, where it consistently achieves smaller coresets than existing state-of-the-art methods, even without explicitly enforcing the assumptions used in the analysis.

Abstract

Clustering

Explore similar work

Beyond Worst-Case Coreset Bounds for kkk-Clustering via Determinantal Sampling

EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

Beyond Worst-Case Coreset Bounds for $k$ -Clustering via Determinantal Sampling