# A Tight VC-Dimension Analysis of Clustering Coresets with Applications

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 49 references that are in the map.
- First posted on arXiv 11 Jan 2025.

## Builds on (most cited first, 26 of 26)

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Coresets for Clustering in Excluded-minor Graphs and Beyond](https://mlsanity.com/paper/2004.07718/) (2020)
- [Coresets for Clustering in Graphs of Bounded Treewidth](https://mlsanity.com/paper/1907.04733/) (2019)
- [Fully-Dynamic Coresets](https://mlsanity.com/paper/2004.14891/) (2020)
- [On Optimal Coreset Construction for Euclidean (k,z)-Clustering](https://mlsanity.com/paper/2211.11923/) (2022)
- [Coresets for Ordered Weighted Clustering](https://mlsanity.com/paper/1903.04351/) (2019)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Streaming Euclidean k-median and k-means with o(log n) Space](https://mlsanity.com/paper/2310.02882/) (2023)
- [Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds](https://mlsanity.com/paper/2405.01339/) (2024)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [On Coresets for Clustering in Small Dimensional Euclidean Spaces](https://mlsanity.com/paper/2302.13737/) (2023)
- [VC Set Systems in Minor-free (Di)Graphs and Applications](https://mlsanity.com/paper/2304.01790/) (2023)
- [Solving Proximity Problems for Polygonal Shapes via Polynomials](https://mlsanity.com/paper/2308.05998/) (2023)
- [The VC Dimension of Metric Balls under Fr'echet and Hausdorff Distances](https://mlsanity.com/paper/1903.03211/) (2019)
- [Solving Fr'echet Distance Problems by Algebraic Geometric Methods](https://mlsanity.com/paper/2308.14569/) (2023)
- [Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation](https://mlsanity.com/paper/2310.04076/) (2023)
- [Fast Approximations and Coresets for (k, l)-Median under Dynamic Time Warping](https://mlsanity.com/paper/2312.09838/) (2023)
- [Coresets for Clustering in Geometric Intersection Graphs](https://mlsanity.com/paper/2303.01400/) (2023)

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

- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves](https://mlsanity.com/paper/2505.23431/) (2025)
- [SubZeroCore: A Submodular Approach with Zero Training for Coreset Selection](https://mlsanity.com/paper/2509.21748/) (2025)
- [Dimension Reduction for Curves: Simplified and Generalized](https://mlsanity.com/paper/2607.03112/) (2026)

## Abstract (arXiv)

We consider coresets for k-clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the k-median objective sumpminc∈ Cdist(p,C). Given a point set P, a coreset Omega is a small weighted subset that approximates the cost of P for all candidate solutions C up to a (1±varepsilon ) multiplicative factor. In this paper, we give a sharp VC-dimension based analysis for coreset construction. As a consequence, we obtain improved k-median coreset bounds for the following metrics: Coresets of size tildeOleft(kvarepsilon-2right) for shortest path metrics in planar graphs, improving over the bounds tildeOleft(kvarepsilon-6right) by [Cohen-Addad, Saulpic, Schwiegelshohn, STOC'21] and tildeOleft(k2varepsilon-4right) by [Braverman, Jiang, Krauthgamer, Wu, SODA'21]. Coresets of size tildeOleft(kdℓvarepsilon-2log mright) for clustering d-dimensional polygonal curves of length at most m with curves of length at most ℓ with respect to Frechet metrics, improving over the bounds tildeOleft(k3dℓvarepsilon-3log mright) by [Braverman, Cohen-Addad, Jiang, Krauthgamer, Schwiegelshohn, Toftrup, and Wu, FOCS'22] and tildeOleft(k2dℓvarepsilon-2log m log |P|right) by [Conradi, Kolbe, Psarros, Rohde, SoCG'24].