# On Optimal Coreset Construction for Euclidean (k,z)-Clustering

arXiv: https://arxiv.org/abs/2211.11923 · HTML: https://mlsanity.com/paper/2211.11923/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2022.

## Built on by (most cited first, 9 of 9)

- [Small coresets via negative dependence: DPPs, linear statistics, and concentration](https://mlsanity.com/paper/2411.00611/) (2024)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Advancing Complex Wide-Area Scene Understanding with Hierarchical Coresets Selection](https://mlsanity.com/paper/2507.13061/) (2025)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)
- [Coresets for Clustering Under Stochastic Noise](https://mlsanity.com/paper/2510.23438/) (2025)
- [Omnimodal Dataset Distillation via High-order Proxy Alignment](https://mlsanity.com/paper/2604.10666/) (2026)
- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)

## Abstract (arXiv)

Constructing small-sized coresets for various clustering problems in different metric spaces has attracted significant attention for the past decade. A central problem in the coreset literature is to understand what is the best possible coreset size for (k,z)-clustering in Euclidean space. While there has been significant progress in the problem, there is still a gap between the state-of-the-art upper and lower bounds. For instance, the best known upper bound for k-means (z=2) is min O(k3/2 varepsilon-2),O(k varepsilon-4) [1,2], while the best known lower bound is Omega(kvarepsilon-2) [1]. In this paper, we make significant progress on both upper and lower bounds. For a large range of parameters (i.e., varepsilon, k), we have a complete understanding of the optimal coreset size. In particular, we obtain the following results: (1) We present a new coreset lower bound Omega(k varepsilon-z-2) for Euclidean (k,z)-clustering when varepsilon ≥ Omega(k-1/(z+2)). In view of the prior upper bound tildeOz(k varepsilon-z-2) [1], the bound is optimal. The new lower bound also implies improved lower bounds for (k,z)-clustering in doubling metrics. (2) For the upper bound, we provide efficient coreset construction algorithms for (k,z)-clustering with improved or optimal coreset sizes in several metric spaces. In particular, we provide an tildeOz(k^frac2z+2z+2 varepsilon-2)-sized coreset, with a unfied analysis, for (k,z)-clustering for all z≥ 1 in Euclidean space. [1] Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC'22. [2] Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS'22.