# Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2020.

## Built on by (most cited first, 30 of 31)

- [Coverage-centric Coreset Selection for High Pruning Rates](https://mlsanity.com/paper/2210.15809/) (2022)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [You Only Condense Once: Two Rules for Pruning Condensed Datasets](https://mlsanity.com/paper/2310.14019/) (2023)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [Coresets for Time Series Clustering](https://mlsanity.com/paper/2110.15263/) (2021)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [DataS^3: Dataset Subset Selection for Specialization](https://mlsanity.com/paper/2504.16277/) (2025)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [A Batch-to-Online Transformation under Random-Order Model](https://mlsanity.com/paper/2306.07163/) (2023)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Socially Fair Center-based and Linear Subspace Clustering](https://mlsanity.com/paper/2208.10095/) (2022)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [Structure-Aware Spectral Sparsification via Uniform Edge Sampling](https://mlsanity.com/paper/2510.12669/) (2025)
- [Efficient NTK using Dimensionality Reduction](https://mlsanity.com/paper/2210.04807/) (2022)
- [Improved Coresets for Euclidean k-Means](https://mlsanity.com/paper/2211.08184/) (2022)
- [Universal Weak Coreset](https://mlsanity.com/paper/2305.16890/) (2023)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)
- [Coresets for Multiple ℓp Regression](https://mlsanity.com/paper/2406.02432/) (2024)
- [Coreset Spectral Clustering](https://mlsanity.com/paper/2503.07227/) (2025)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

Given a collection of n points in ℝd, the goal of the (k,z)-clustering problem is to find a subset of k "centers" that minimizes the sum of the z-th powers of the Euclidean distance of each point to the closest center. Special cases of the (k,z)-clustering problem include the k-median and k-means problems. Our main result is a unified two-stage importance sampling framework that constructs an varepsilon-coreset for the (k,z)-clustering problem. Compared to the results for (k,z)-clustering in [Feldman and Langberg, STOC 2011], our framework saves a varepsilon2 d factor in the coreset size. Compared to the results for (k,z)-clustering in [Sohler and Woodruff, FOCS 2018], our framework saves a operatornamepoly(k) factor in the coreset size and avoids the exp(k/varepsilon) term in the construction time. Specifically, our coreset for k-median (z=1) has size tildeO(varepsilon-4 k) which, when compared to the result in [Sohler and Woodruff, STOC 2018], saves a k factor in the coreset size. Our algorithmic results rely on a new dimensionality reduction technique that connects two well-known shape fitting problems: subspace approximation and clustering, and may be of independent interest. We also provide a size lower bound of Omegaleft(k· min left2z/20,d rightright) for a 0.01-coreset for (k,z)-clustering, which has a linear dependence of size on k and an exponential dependence on z that matches our algorithmic results.