# A Nearly Tight Analysis of Greedy k-means++

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 16 Jul 2022.

## Builds on (most cited first, 11 of 11)

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [k-means++: few more steps yield constant approximation](https://mlsanity.com/paper/2002.07784/) (2020)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Improved Guarantees for k-means++ and k-means++ Parallel](https://mlsanity.com/paper/2010.14487/) (2020)
- [A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++](https://mlsanity.com/paper/1605.04986/) (2016)
- [Adapting k-means algorithms for outliers](https://mlsanity.com/paper/2007.01118/) (2020)
- [Noisy, Greedy and Not So Greedy k-means++](https://mlsanity.com/paper/1912.00653/) (2019)
- [Simple and sharp analysis of k-means||](https://mlsanity.com/paper/2003.02518/) (2020)

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

- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [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)
- [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025)
- [CINNAMON: A hybrid approach to change point detection and parameter estimation in single-particle tracking data](https://mlsanity.com/paper/2503.14253/) (2025)
- [CORE-ReID V2: Advancing the Domain Adaptation for Object Re-Identification with Optimized Training and Ensemble Fusion](https://mlsanity.com/paper/2508.04036/) (2025)
- [Randomizing the Number of Centers in k-means++](https://mlsanity.com/paper/2607.26202/) (2026)

## Abstract (arXiv)

The famous k-means++ algorithm of Arthur and Vassilvitskii [SODA 2007] is the most popular way of solving the k-means problem in practice. The algorithm is very simple: it samples the first center uniformly at random and each of the following k-1 centers is then always sampled proportional to its squared distance to the closest center so far. Afterward, Lloyd's iterative algorithm is run. The k-means++ algorithm is known to return a Theta(log k) approximate solution in expectation. In their seminal work, Arthur and Vassilvitskii [SODA 2007] asked about the guarantees for its following greedy variant: in every step, we sample ℓ candidate centers instead of one and then pick the one that minimizes the new cost. This is also how k-means++ is implemented in e.g. the popular Scikit-learn library [Pedregosa et al.; JMLR 2011]. We present nearly matching lower and upper bounds for the greedy k-means++: We prove that it is an O(ℓ3 log3 k)-approximation algorithm. On the other hand, we prove a lower bound of Omega(ℓ3 log3 k / log2(ℓlog k)). Previously, only an Omega(ℓ log k) lower bound was known [Bhattacharya, Eube, R"oglin, Schmidt; ESA 2020] and there was no known upper bound.