mlsanityData to 7 Oct 2026

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

arXiv 2204.04828 ↗First posted 11 Apr 2022cs.DS cs.CG cs.LGcited by 14

Not on the map. Why?

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.

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

Builds on

14 of 45 references.

References · 14

  1. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  2. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  3. 2014An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimizationcited by 26
  4. 2015The Hardness of Approximation of Euclidean k-meanscited by 25
  5. 2015Improved and Simplified Inapproximability for k-meanscited by 22
  6. 2018Near-Linear Time Approximation Schemes for Clustering in Doubling Metricscited by 14
  7. 2020On Approximability of Clustering Problems Without Candidate Centerscited by 13
  8. 2017A Fast Approximation Scheme for Low-Dimensional k-Meanscited by 10
  9. 2021An Improved Local Search Algorithm for k-Mediancited by 8
  10. 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
  11. 2019Tight FPT Approximations for k-Median and k-Meanscited by 7
  12. 2021A Refined Approximation for Euclidean k-Meanscited by 7
2 more
  1. 2015A bi-criteria approximation algorithm for k Meanscited by 4
  2. 2015On Variants of k-means Clusteringcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 3; 2025: 2; 2026: 2.

14 papers.

Sort:

  1. 2023Replicable Clusteringcited by 19
  2. 2024A Scalable Algorithm for Individually Fair K-means Clusteringcited by 8
  3. 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
  4. 2023Multi-Swap k-Means++cited by 4
  5. 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithmscited by 3
  6. 2023Parameterized Approximation for Robust Clustering in Discrete Geometric Spacescited by 2
  7. 2025Differentially Private Wasserstein Barycenterscited by 2
  8. 2023Impossibility of Depth Reduction in Explainable Clusteringcited by 1
  9. 2023Differential Privacy for Clustering Under Continual Observationcited by 1
  10. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  11. 2024Faster and Simpler Greedy Algorithm for k-Median and k-Meanscited by 0
  12. 2025Learning Augmented Graph k-Clusteringcited by 0
2 more
  1. 2026Simple KNN-Based Outlier Detection Achieves Robust Clusteringcited by 0
  2. 2026Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesycited by 0