betaFeedback

WorksComputer Science

Coresets for Capacitated Clustering via Dual Concentration

Abstract

We study coresets for clustering problems, focusing on the classical kk-median and kk-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 kk 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.

Statement on AI Use. The perspective of using the dual for concentration, rather than the primal, was pointed out by ChatGPT-5.5 Pro. In addition, the authors used AI to help polish the writing, review the proofs, and check the manuscript for possible errors, in multiple rounds of prompting. All content was carefully examined by the authors, who take full responsibility for the content of the manuscript.

Introduction

Coresets are a staple of big data algorithms. Given a loss function, a point set PP, and a set of candidate solutions C\mathcal{C}, a coreset Q⊆PQ \subseteq P is a significantly smaller weighted set such that, for all C∈CC \in\mathcal{C},

cost⁡(Q,C)=(1±ε)cost⁡(P,C).\operatorname{cost}(Q,C)=(1\pm\varepsilon)\operatorname{cost}(P,C).

For a fixed accuracy parameter ε\varepsilon, the quality of a coreset algorithm is measured by the number of distinct points in QQ, which we call its size.

In this paper, we study coresets for center-based clustering where we are typically interested in objectives of the form ∑p∈Pdz(p,C(p))\sum_{p\in P}d^z(p,C(p)), where dd is the distance function of the underlying metric and C(p)C(p) is the center to which pp is assigned from a set CC of at most kk centers. The most important special cases, z=1z=1 and z=2z=2, are known as kk-median and kk-means, respectively. For the unconstrained variants, where C(p)=arg⁡min⁡c∈Cd(p,c)C(p)=\arg\min_{c\in C}d(p,c), the coreset problem is now well understood. Specifically, for finite NN-point metrics, coresets of size O~(kε−2log⁡N)\widetilde{O}(k\varepsilon^{-2}\log N) are known [20, 15]; in Euclidean spaces, coresets of size O~(kε−2min⁡(kz/(z+2),ε−z))\widetilde{O}(k\varepsilon^{-2}\min(k^{z/(z+2)},\varepsilon^{-z})) are known [13, 29]. These bounds are optimal up to logarithmic factors [14, 29]. A more detailed review of coreset bounds for different metric spaces appears in Section A.

The situation is markedly different for constrained variants of these problems. A central example is cardinality-constrained clustering. In this paper we use the standard fractional transportation formulation: given a demand vector h∈nΔkh\in n\Delta_k, the objective is to minimize the kk-median or kk-means cost over assignments xp,i∈[0,1]x_{p,i}\in[0,1] such that each point p∈Pp\in P is assigned total mass ∑i=1kxp,i=1\sum_{i=1}^{k}x_{p,i}=1, and each center cic_i receives total mass ∑p∈Pxp,i=hi\sum_{p\in P}x_{p,i}=h_i. For unweighted point sets and integral demands, this coincides with the usual requirement that exactly hih_i points are assigned to cic_i.

Our coreset guarantee preserves this objective simultaneously for every choice of centers CC and every demand vector hh. Consequently, it also preserves the optimum over any feasible family of demand vectors. Via known reductions, see Proposition C.1, this yields coresets for widely studied constrained clustering problems, including upper- and lower-capacitated clustering, fair clustering, and clustering with anonymity constraints.

Having established that the same coreset framework applies to these constrained variants, we next ask how large such coresets must be. More precisely, we are interested in the dependence of the coreset size on the main problem parameters, such as kk, the accuracy parameter ε\varepsilon, and the dimension or metric size. This dependence is difficult to summarize succinctly. The most important barrier is that all known constructions have at least quadratic dependence on kk [7, 5, 12, 28], in addition to non-optimal dependencies on other parameters. Such a quadratic dependence has historically been a major barrier even for unconstrained clustering; for cardinality-constrained clustering, it has so far proven formidable. At the same time, there is no evidence that cardinality constraints should force larger coresets than in the unconstrained setting. Thus, the guiding question of this paper is:

Do cardinality constraints fundamentally change coreset sizes for clustering?

Our Results

In this paper, we give strong evidence that the answer may be negative in general and resolve the question for finite metrics. Notably, our first main result is:

Theorem 1.1. There exists a coreset for kk-median and kk-means with cardinality constraints in finite NN-point metrics of size O(kε−2log⁡N)O(k\varepsilon^{-2}\log N).

This bound matches the best-known lower bounds for unconstrained kk-median and kk-means in finite metrics [14], and is therefore optimal up to constant factors. Combining our finite-metric coreset with previous techniques for cardinality-constrained coreset construction already gives improved Euclidean bounds over prior work [5, 28]; see § 3. However, this black-box route still has quadratic dependence on kk. Our second main result breaks the quadratic barrier in kk, with no dependence on the dimension dd or the input size nn.

Theorem 1.2. There exists a coreset for kk-median (z=1z = 1) and kk-means (z=2z = 2) with cardinality constraints in dd-dimensional Euclidean spaces of size O~(kε−2−2z)\widetilde{O}(k\varepsilon^{-2-2z}).

This does not match the known lower bounds for Euclidean clustering [29]. Nevertheless, to the best of our knowledge, it is the first cardinality-constrained coreset construction to combine near-linear dependence on kk with competitive ε\varepsilon-dependence. The algorithms are efficient with the bottleneck being the computation of a constant-factor approximation.

ReferenceCoreset Size (kk-median, kk-means)
Cohen-Addad, Li [12]O~(k2ε−5log⁡2n)\widetilde{O}(k^{2}\varepsilon^{-5}\log^{2}n) O~(k5ε−5log⁡2n)\widetilde{O}(k^{5}\varepsilon^{-5}\log^{2}n)
Schmidt, Schwiegelshohn, Sohler [SSS19]O(kε−d−1log⁡n)O(k\varepsilon^{-d-1}\log n) O(kε−d−2log⁡n)O(k\varepsilon^{-d-2}\log n)
Huang, Jiang, Vishnoi [25]O~(k2ε−d)\widetilde{O}(k^{2}\varepsilon^{-d}) O~(k3ε−d−1)\widetilde{O}(k^{3}\varepsilon^{-d-1})
Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, Wu [5]O~(k3ε−6)\widetilde{O}(k^{3}\varepsilon^{-6}) O~(k7ε−10)\widetilde{O}(k^{7}\varepsilon^{-10})
Huang, Li, Lu, Wu [28]O~(k2ε−4)\widetilde{O}(k^{2}\varepsilon^{-4}) O~(k2ε−6)\widetilde{O}(k^{2}\varepsilon^{-6})
This paperO~(kε−4)\widetilde{O}(k\varepsilon^{-4}) O~(kε−6)\widetilde{O}(k\varepsilon^{-6})

Table 1. Coreset size bounds for cardinality-constrained clustering in dd-dimensional Euclidean space. For each reference, the first bound is for kk-median and the second is for kk-means.

Preliminaries and Definitions

Notation. We use a≲ba \lesssim b to denote a≤ηba \leq\eta b for some absolute constant η\eta. For an integer mm, write [m]={1,…,m}[m] = \{1,\ldots,m\}. Let Δk={x∈Rk:x≥0, ∑ixi=1}\Delta_k = \{x \in\mathbb{R}^k : x \geq0,\ \sum_i x_i = 1\} denote the kk-dimensional unit simplex.

The kk-median Objective with Cardinality Constraints. Let (X,d)(X,d) be a metric space. We first define the objective for a generic weighted instance S⊆XS \subseteq X of total weight nn. We write wS(s)w_S(s) for the weight of s∈Ss \in S and n=∑s∈SwS(s)n = \sum_{s \in S} w_S(s) to denote the total weight of the instance.

Fix an ordered center tuple C=(c1,…,ck)∈XkC = (c_1,\ldots,c_k) \in X^k and a demand vector h∈nΔkh \in n\Delta_k. The coordinate hih_i is the demand of center cic_i. For this demand vector hh, the cardinality-constrained assignment cost, denoted by cost⁡S(C,h)\operatorname{cost}_S(C,h), is the cost of the cheapest fractional assignment of points in SS to the centers in CC that respects the demands hh. Formally, it is the value of the following LP.

Primal assignment LP
cost⁡S(C,h)=min⁡x∑s,ixs,id(s,ci)\operatorname{cost}_S(C,h)=\min_x \sum_{s,i} x_{s,i}d(s,c_i)
s.t.∑i∈[k]xs,i=wS(s)s∈S,\text{s.t.}\quad\sum_{i\in[k]}x_{s,i}=w_S(s)\quad s\in S,
∑s∈Sxs,i=hii∈[k],\sum_{s\in S}x_{s,i}=h_i\quad i\in[k],
xs,i≥0s∈S, i∈[k].x_{s,i}\ge0\quad s\in S,\ i\in[k].
Dual assignment LP
max⁡α∈RS, β∈Rk∑s∈SwS(s)αs−h⋅β\max_{\alpha\in\mathbb{R}^S,\ \beta\in\mathbb{R}^k}\sum_{s\in S}w_S(s)\alpha_s-h\cdot\beta
s.t.αs≤d(s,ci)+βis∈S, i∈[k].\text{s.t.}\quad\alpha_s\le d(s,c_i)+\beta_i\quad s\in S,\ i\in[k].

Table 1 (PDF p. 4).

The dual of the above LP, written alongside, will be important in the analysis later in the paper. The key reason for this is that it can be expressed succinctly. In particular, we can eliminate the auxiliary variables αs\alpha_s. For a fixed β∈Rk\beta\in\mathbb{R}^k, the optimal choice of αs\alpha_s is

fC,β(s)=min⁡i∈[k]{d(s,ci)+βi}.f_{C,\beta}(s)=\min_{i\in[k]}\{d(s,c_i)+\beta_i\}.

Thus the reduced dual objective is

Dual⁡S(C,h,β)=∑s∈SwS(s)fC,β(s)−h⋅β.(1)\operatorname{Dual}_S(C,h,\beta)=\sum_{s\in S}w_S(s)f_{C,\beta}(s)-h\cdot\beta. \tag*{(1)}

We now note the following consequence of strong duality.

Claim 2.1 (Strong duality). For every weighted instance S⊆XS\subseteq X of total weight nn, every center tuple C=(c1,…,ck)∈XkC=(c_1,\ldots,c_k)\in X^k, and every demand vector h∈nΔkh\in n\Delta_k,

cost⁡S(C,h)=sup⁡β∈RkDual⁡S(C,h,β).\operatorname{cost}_S(C,h)=\sup_{\beta\in\mathbb{R}^k}\operatorname{Dual}_S(C,h,\beta).

References

  1. [1][AB99] Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
  2. [2][AS24] Peyman Afshani and Chris Schwiegelsohn. Optimal coresets for low-dimensional geometric median. In Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21–27, 2024, volume 235 of Proceedings of Machine Learning Research, pages 262–270. PMLR / OpenReview.net, 2024.
  3. [3][BBC+19] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelsohn. Oblivious dimension reduction for k-means: beyond subspaces and the johnson–lindenstrauss lemma. In Symposium on Theory of Computing, STOC, pages 1039–1050, 2019.DOI
  4. [4][BBH+20] Daniel N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in graphs of bounded treewidth. In International Conference on Machine Learning, ICML, pages 569–579, 2020.arxiv.org/abs/1907.04733
  5. [5]Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In Symposium on Foundations of Computer Science, FOCS, pages 462–473, 2022.arxiv.org/abs/2209.01901
  6. [6]Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: Worst case and stability optimal coreset bounds. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 1707–1723. IEEE, 2024.arxiv.org/abs/2405.01339
  7. [7]Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and euclidean spaces and their applications. In Intl. Colloquium on Automata, Languages, and Programming, ICALP, pages 23:1–23:15, 2021.
  8. [8]Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In Symposium on Discrete Algorithms, SODA 2021, pages 2679–2696, 2021.arxiv.org/abs/2004.07718
  9. [9]Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, and Chris Schwiegelshohn. A tight vc-dimension analysis of clustering coresets with applications. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4783–4808. SIAM, 2025.
  10. [10]Ke Chen. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput., 39(3):923–947, 2009.DOI
  11. [11]Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde. Fast approximations and coresets for (k,l)-median under dynamic time warping. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th International Symposium on Computational Geometry, SoCG 2024, Athens, Greece, June 11-14, 2024, volume 293 of LIPIcs, pages 42:1–42:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
  12. [12]Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In International Colloquium on Automata, Languages, and Programming, ICALP, pages 41:1–41:14, 2019.
  13. [13]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for euclidean k-means. In NeurIPS, 2022.
  14. [14]Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Symposium on Theory of Computing, STOC, pages 1038–1051, 2022.
  15. [15]Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Symposium on Theory of Computing, STOC, pages 169–182, 2021.
  16. [17][CWWZ25] Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, and Samson Zhou. Fast, space-optimal streaming algorithms for clustering and subspace embeddings. CoRR, abs/2504.16229, 2025.
  17. [18][DSS24] Andrew Draganov, David Saulpic, and Chris Schwiegelsohn. Settling time vs. accuracy tradeoffs for clustering big data. Proc. ACM Manag. Data, 2(3):173, 2024.arxiv.org/abs/2404.01936
  18. [19][FKW21] Zhili Feng, Praneeth Kacham, and David P. Woodruff. Dimensionality reduction for the sum-of-distances metric. In International Conference on Machine Learning, ICML, pages 3220–3229, 2021.
  19. [20][FL11] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Symposium on Theory of Computing, STOC, pages 569–578, 2011.
  20. [21][FS05] Gereon Frahling and Christian Sohler. Coresets in dynamic geometric data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 209–217, 2005.DOI
  21. [22][FSS20] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering. SIAM J. Comput., 49(3):601–657, 2020.
  22. [23][HHHW23] Lingxiao Huang, Ruiyuan Huang, Zengfeng Huang, and Xuan Wu. On coresets for clustering in small dimensional euclidean spaces. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 13891–13915. PMLR, 2023.arxiv.org/abs/2302.13737
  23. [24][HJLW18] Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. Epsilon-coresets for clustering (with outliers) in doubling metrics. In Symposium on Foundations of Computer Science, FOCS, pages 814–825, 2018.DOI
  24. [25][HJV19] Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheet K. Vishnoi. Coresets for clustering with fairness constraints. In Neural Information Processing Systems, NeurIPS, pages 7587–7598, 2019.arxiv.org/abs/1906.08484
  25. [26][HK07] Sariel Har-Peled and Akash Kushal. Smaller coresets for k-median and k-means clustering. Discrete & Computational Geometry, 37(1):3–19, 2007.
  26. [27][HK20] Monika Henzinger and Sagar Kale. Fully-dynamic coresets. In Fabrizio Grandoni, Gregorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, Pisa, Italy (Virtual Conference), September 7-9, 2020, volume 173 of LIPIcs, pages 57:1–57:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.arxiv.org/abs/2004.14891
  27. [28][HLLW25] Lingxiao Huang, Jian Li, Pinyan Lu, and Xuan Wu. Coresets for constrained clustering: General assignment constraints and improved size bounds. In Yossi Azar and Debmalyа Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4732–4782. SIAM, 2025.arxiv.org/abs/2301.08460
  28. [29]Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for euclidean (k, z)-clustering. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024, pages 1594–1604. ACM, 2024.arxiv.org/abs/2211.11923
  29. [30]Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Symposium on Theory of Computing, STOC, pages 291–300, 2004.
  30. [32]Michael Langberg and Leonard J. Schulman. Universal ε-approximators for integrals. In Symposium on Discrete Algorithms, SODA, pages 598–607, 2010.
  31. [33]Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson-lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1027–1038, 2019.
  32. [35]Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in euclidean space. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1064–1069, 2019.arxiv.org/abs/1810.09250
  33. [40]Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In Symposium on Foundations of Computer Science, FOCS, pages 802–813, 2018.arxiv.org/abs/1809.02961
  34. [41]Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer Series in Statistics. Springer, 1996.
  35. [42]Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2 edition, 2026.
  36. [43]H. E. Warren. Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society, 133:167–178, 1968.DOI

Paper details

vlnc:W_rk47bx5q
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT-5.5 Pro, GPT-5.5 (bare)

View statement
Looking for related papers…
Contents