mlsanityData to 7 Oct 2026

Improved and Simplified Inapproximability for k-means

arXiv 1509.00916 ↗First posted 3 Sep 2015cs.CGcited by 22

Not on the map. Why?

Abstract (arXiv)

The k-means problem consists of finding k centers in the d-dimensional Euclidean space that minimize the sum of the squared distances of all points in an input set P to their closest respective center. Awasthi et. al. recently showed that there exists a constant c > 1 such that it is NP-hard to approximate the k-means objective within a factor of c. We establish that the constant c is at least 1.0013.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Sep 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 7; 2023: 2; 2024: 3; 2025: 1; 2026: 1.

22 papers.

Sort:

By area:

  1. 2021Learning-Augmented k-means Clusteringcited by 26
  2. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  3. 2022Machine Unlearning of Federated Clusterscited by 21
  4. 2021Differentially-Private Clustering of Easy Instancescited by 17
  5. 2022New Coresets for Projective Clustering and Applicationscited by 16
  6. 2021Explainable k-means. Don't be greedy, plant bigger trees!cited by 15
  7. 2022Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Setscited by 14
  8. 2021Near-optimal Algorithms for Explainable k-Medians and k-Meanscited by 13
  9. 2021Dimensionality Reduction for Wasserstein Barycentercited by 13
  10. 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
  11. 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
  12. 2022A Faster k-means++ Algorithmcited by 4
10 more
  1. 2023Multi-Swap k-Means++cited by 4
  2. 2023Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorizationcited by 3
  3. 2021Coresets for constrained k-median and k-means clustering in low dimensional Euclidean spacecited by 2
  4. 2022Tackling Provably Hard Representative Selection via Graph Neural Networkscited by 2
  5. 2021Differentially Private Algorithms for Clustering with Stability Assumptionscited by 1
  6. 2024Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problemscited by 1
  7. 2024On Approximability of ℓ22 Min-Sum Clusteringcited by 1
  8. 2024A cutting plane algorithm for globally solving low dimensional k-means clustering problemscited by 0
  9. 2025Learning Augmented Graph k-Clusteringcited by 0
  10. 2026A Sub-4 Approximation for Fair k-Meanscited by 0