# A Fast Approximation Scheme for Low-Dimensional k-Means

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Aug 2017.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [A Faster k-means++ Algorithm](https://mlsanity.com/paper/2211.15118/) (2022)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Faster and Simpler Greedy Algorithm for k-Median and k-Means](https://mlsanity.com/paper/2407.11217/) (2024)

## Abstract (arXiv)

We consider the popular k-means problem in d-dimensional Euclidean space. Recently Friggstad, Rezapour, Salavatipour [FOCS'16] and Cohen-Addad, Klein, Mathieu [FOCS'16] showed that the standard local search algorithm yields a (1+ε)-approximation in time (n · k)^1/εO(d), giving the first polynomial-time approximation scheme for the problem in low-dimensional Euclidean space. While local search achieves optimal approximation guarantees, it is not competitive with the state-of-the-art heuristics such as the famous k-means++ and D2-sampling algorithms. In this paper, we aim at bridging the gap between theory and practice by giving a (1+ε)-approximation algorithm for low-dimensional k-means running in time n · k · (log n)^(dε-1)O(d), and so matching the running time of the k-means++ and D2-sampling heuristics up to polylogarithmic factors. We speed-up the local search approach by making a non-standard use of randomized dissections that allows to find the best local move efficiently using a quite simple dynamic program. We hope that our techniques could help design better local search heuristics for geometric problems. We note that the doubly exponential dependency on d is necessary as k-means is APX-hard in dimension d = ω(log n).