# Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 11 Apr 2022.

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

- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics](https://mlsanity.com/paper/1812.08664/) (2018)
- [On Approximability of Clustering Problems Without Candidate Centers](https://mlsanity.com/paper/2010.00087/) (2020)
- [A Fast Approximation Scheme for Low-Dimensional k-Means](https://mlsanity.com/paper/1708.07381/) (2017)
- [An Improved Local Search Algorithm for k-Median](https://mlsanity.com/paper/2111.04589/) (2021)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Tight FPT Approximations for k-Median and k-Means](https://mlsanity.com/paper/1904.12334/) (2019)
- [A Refined Approximation for Euclidean k-Means](https://mlsanity.com/paper/2107.07358/) (2021)
- [A bi-criteria approximation algorithm for k Means](https://mlsanity.com/paper/1507.04227/) (2015)
- [On Variants of k-means Clustering](https://mlsanity.com/paper/1512.02985/) (2015)

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

- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [A Scalable Algorithm for Individually Fair K-means Clustering](https://mlsanity.com/paper/2402.06730/) (2024)
- [A Nearly Tight Analysis of Greedy k-means++](https://mlsanity.com/paper/2207.07949/) (2022)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023)
- [Differential Privacy for Clustering Under Continual Observation](https://mlsanity.com/paper/2307.03430/) (2023)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming](https://mlsanity.com/paper/2310.19068/) (2023)
- [Faster and Simpler Greedy Algorithm for k-Median and k-Means](https://mlsanity.com/paper/2407.11217/) (2024)
- [Learning Augmented Graph k-Clustering](https://mlsanity.com/paper/2506.13533/) (2025)
- [Simple KNN-Based Outlier Detection Achieves Robust Clustering](https://mlsanity.com/paper/2605.07130/) (2026)
- [Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy](https://mlsanity.com/paper/2608.14215/) (2026)

## Abstract (arXiv)

Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean k-median and k-means problems. We propose a new primal-dual algorithm, inspired by the classic algorithm of Jain and Vazirani and the recent algorithm of Ahmadian, Norouzi-Fard, Svensson, and Ward. Our algorithm achieves an approximation ratio of 2.406 and 5.912 for Euclidean k-median and k-means, respectively, improving upon the 2.633 approximation ratio of Ahmadian et al. and the 6.1291 approximation ratio of Grandoni, Ostrovsky, Rabani, Schulman, and Venkat. Our techniques involve a much stronger exploitation of the Euclidean metric than previous work on Euclidean clustering. In addition, we introduce a new method of removing excess centers using a variant of independent sets over graphs that we dub a "nested quasi-independent set". In turn, this technique may be of interest for other optimization problems in Euclidean and ℓp metric spaces.