# A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2016.

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

- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [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)
- [A Faster k-means++ Algorithm](https://mlsanity.com/paper/2211.15118/) (2022)
- [Distributed k-Means with Outliers in General Metrics](https://mlsanity.com/paper/2202.08173/) (2022)
- [An Analysis of Dα seeding for k-means](https://mlsanity.com/paper/2310.13474/) (2023)
- [Randomizing the Number of Centers in k-means++](https://mlsanity.com/paper/2607.26202/) (2026)

## Abstract (arXiv)

This paper studies the k-means++ algorithm for clustering as well as the class of Dℓ sampling algorithms to which k-means++ belongs. It is shown that for any constant factor β > 1, selecting β k cluster centers by Dℓ sampling yields a constant-factor approximation to the optimal clustering with k centers, in expectation and without conditions on the dataset. This result extends the previously known O(log k) guarantee for the case β = 1 to the constant-factor bi-criteria regime. It also improves upon an existing constant-factor bi-criteria result that holds only with constant probability.