mlsanityData to 14 Oct 2026

A Tight VC-Dimension Analysis of Clustering Coresets with Applications

arXiv 2501.06588 ↗First posted 11 Jan 2025cs.CG cs.DS cs.LGcited by 4

Not on the map. Why?

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].

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

26 of 49 references.

References · 26

  1. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  2. 2018On Coresets for Logistic Regressioncited by 67
  3. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  4. 2019Coresets for Clustering with Fairness Constraintscited by 51
  5. 2021A New Coreset Framework for Clusteringcited by 38
  6. 2020Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimalcited by 31
  7. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  8. 2018varepsilon-Coresets for Clustering (with Outliers) in Doubling Metricscited by 19
  9. 2022The Power of Uniform Sampling for Coresetscited by 18
  10. 2020Coresets for Clustering in Excluded-minor Graphs and Beyondcited by 14
  11. 2019Coresets for Clustering in Graphs of Bounded Treewidthcited by 9
  12. 2020Fully-Dynamic Coresetscited by 9
14 more
  1. 2022On Optimal Coreset Construction for Euclidean (k,z)-Clusteringcited by 9
  2. 2019Coresets for Ordered Weighted Clusteringcited by 8
  3. 2022An Empirical Evaluation of k-Means Coresetscited by 7
  4. 2023Streaming Euclidean k-median and k-means with o(log n) Spacecited by 7
  5. 2024Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Boundscited by 5
  6. 2024Settling Time vs. Accuracy Tradeoffs for Clustering Big Datacited by 4
  7. 2023On Coresets for Clustering in Small Dimensional Euclidean Spacescited by 3
  8. 2023VC Set Systems in Minor-free (Di)Graphs and Applicationscited by 3
  9. 2023Solving Proximity Problems for Polygonal Shapes via Polynomialscited by 3
  10. 2019The VC Dimension of Metric Balls under Fr'echet and Hausdorff Distancescited by 2
  11. 2023Solving Fr'echet Distance Problems by Algebraic Geometric Methodscited by 2
  12. 2023Deterministic Clustering in High Dimensional Spaces: Sketches and Approximationcited by 2
  13. 2023Fast Approximations and Coresets for (k, l)-Median under Dynamic Time Warpingcited by 2
  14. 2023Coresets for Clustering in Geometric Intersection Graphscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Nearly Tight Regret Bounds for Profit Maximization in Bilateral Tradecited by 7
  2. 2025Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curvescited by 2
  3. 2025SubZeroCore: A Submodular Approach with Zero Training for Coreset Selectioncited by 0
  4. 2026Dimension Reduction for Curves: Simplified and Generalizedcited by 0