mlsanityData to 7 Oct 2026

A New Coreset Framework for Clustering

arXiv 2104.06133 ↗First posted 13 Apr 2021cs.DScited by 38

Not on the map. Why?

Abstract (arXiv)

Given a metric space, the (k,z)-clustering problem consists of finding k centers such that the sum of the of distances raised to the power z of every point to its closest center is minimized. This encapsulates the famous k-median (z=1) and k-means (z=2) clustering problems. Designing small-space sketches of the data that approximately preserves the cost of the solutions, also known as coresets, has been an important research direction over the last 15 years. In this paper, we present a new, simple coreset framework that simultaneously improves upon the best known bounds for a large variety of settings, ranging from Euclidean space, doubling metric, minor-free metric, and the general metric cases.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 Apr 2021.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 7; 2023: 11; 2024: 10; 2025: 4; 2026: 3.

38 papers.

Sort:

By area:

  1. 2022Coverage-centric Coreset Selection for High Pruning Ratescited by 115
  2. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  3. 2024Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyondcited by 15
  4. 2022Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clusteringcited by 14
  5. 2021Tight FPT Approximation for Socially Fair Clusteringcited by 10
  6. 2022Scalable Differentially Private Clustering via Hierarchically Separated Treescited by 10
  7. 2021Coresets for Time Series Clusteringcited by 8
  8. 2022An Empirical Evaluation of k-Means Coresetscited by 7
  9. 2021Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problemscited by 6
  10. 2023Near-Optimal Quantum Coreset Construction Algorithms for Clusteringcited by 6
  11. 2024Scalable Learning of Item Response Theory Modelscited by 6
  12. 2023Parameterized Approximation Schemes for Clustering with General Norm Objectivescited by 5
26 more
  1. 2025AMPO: Active Multi-Preference Optimization for Self-play Preference Selectioncited by 5
  2. 2023Tight Bounds for Volumetric Spanners and Applicationscited by 4
  3. 2023On Generalization Bounds for Projective Clusteringcited by 4
  4. 2024Settling Time vs. Accuracy Tradeoffs for Clustering Big Datacited by 4
  5. 2025A Tight VC-Dimension Analysis of Clustering Coresets with Applicationscited by 4
  6. 2023Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorizationcited by 3
  7. 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithmscited by 3
  8. 2024Approximate Algorithms For k-Sparse Wasserstein Barycenter With Outlierscited by 3
  9. 2024Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentationcited by 3
  10. 2023Parameterized Approximation for Robust Clustering in Discrete Geometric Spacescited by 2
  11. 2023Simple, Scalable and Effective Clustering via One-Dimensional Projectionscited by 2
  12. 2024Ridge Leverage Score Sampling for ℓp Subspace Approximationcited by 2
  13. 2026CoLA: A Choice Leakage Attack Framework to Expose Privacy Risks in Subset Trainingcited by 2
  14. 2022Socially Fair Center-based and Linear Subspace Clusteringcited by 1
  15. 2022Coresets for Relational Data and The Applicationscited by 1
  16. 2023Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outlierscited by 1
  17. 2023Differentially Private Clustering in Data Streamscited by 1
  18. 2024On Approximability of ℓ22 Min-Sum Clusteringcited by 1
  19. 2024Accurate Coresets for Latent Variable Models and Regularized Regressioncited by 1
  20. 2023Universal Weak Coresetcited by 0
  21. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  22. 2024Faster and Simpler Greedy Algorithm for k-Median and k-Meanscited by 0
  23. 2025Guessing Efficiently for Constrained Subspace Approximationcited by 0
  24. 2025Coresets for Clustering Under Stochastic Noisecited by 0
  25. 2026On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clusteringcited by 0
  26. 2026Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Samplingcited by 0