# Improved and Simplified Inapproximability for k-means

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

## Key facts

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

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

- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Machine Unlearning of Federated Clusters](https://mlsanity.com/paper/2210.16424/) (2022)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Dimensionality Reduction for Wasserstein Barycenter](https://mlsanity.com/paper/2110.08991/) (2021)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [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)
- [A Faster k-means++ Algorithm](https://mlsanity.com/paper/2211.15118/) (2022)
- [Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization](https://mlsanity.com/paper/2306.01869/) (2023)
- [Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space](https://mlsanity.com/paper/2106.07319/) (2021)
- [Tackling Provably Hard Representative Selection via Graph Neural Networks](https://mlsanity.com/paper/2205.10403/) (2022)
- [Differentially Private Algorithms for Clustering with Stability Assumptions](https://mlsanity.com/paper/2106.12959/) (2021)
- [Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems](https://mlsanity.com/paper/2411.01115/) (2024)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [A cutting plane algorithm for globally solving low dimensional k-means clustering problems](https://mlsanity.com/paper/2402.13595/) (2024)
- [Learning Augmented Graph k-Clustering](https://mlsanity.com/paper/2506.13533/) (2025)
- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## 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.