# k-means++: few more steps yield constant approximation

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2020.

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

- [TTS-VAR: A Test-Time Scaling Framework for Visual Auto-Regressive Generation](https://mlsanity.com/paper/2507.18537/) (2025)
- [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)
- [Adaptive Methods for Aggregated Domain Generalization](https://mlsanity.com/paper/2112.04766/) (2021)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy](https://mlsanity.com/paper/2206.12895/) (2022)
- [Global k-means++: an effective relaxation of the global k-means clustering algorithm](https://mlsanity.com/paper/2211.12271/) (2022)
- [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025)
- [A3S: A General Active Clustering Method with Pairwise Constraints](https://mlsanity.com/paper/2407.10196/) (2024)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [A statistically consistent measure of semantic uncertainty using Language Models](https://mlsanity.com/paper/2502.00507/) (2025)
- [Improved seeding strategies for k-means and k-GMM](https://mlsanity.com/paper/2506.21291/) (2025)
- [An Analysis of Dα seeding for k-means](https://mlsanity.com/paper/2310.13474/) (2023)
- [Hierarchical Clustering via Local Search](https://mlsanity.com/paper/2405.15983/) (2024)
- [Decoder-Free Supervoxel GNN for Accurate Brain-Tumor Localization in Multi-Modal MRI](https://mlsanity.com/paper/2601.14055/) (2026)
- [Randomizing the Number of Centers in k-means++](https://mlsanity.com/paper/2607.26202/) (2026)

## Abstract (arXiv)

The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approximation in expectation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a constant approximation (in expectation) to the k-means clustering problem. In this paper, we improve their analysis to show that, for any arbitrarily small constant eps > 0, with only eps k additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper.