# Randomizing the Number of Centers in k-means++

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 23 references that are in the map.
- First posted on arXiv 28 Jul 2026.

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

- [k-means++: few more steps yield constant approximation](https://mlsanity.com/paper/2002.07784/) (2020)
- [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)
- [A Nearly Tight Analysis of Greedy k-means++](https://mlsanity.com/paper/2207.07949/) (2022)
- [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)
- [Budget-Smoothed Analysis for Submodular Maximization](https://mlsanity.com/paper/2102.05782/) (2021)
- [Simple and sharp analysis of k-means||](https://mlsanity.com/paper/2003.02518/) (2020)
- [Beyond Worst-Case Budget-Feasible Mechanism Design](https://mlsanity.com/paper/2211.08711/) (2022)
- [Noisy k-means++ Revisited](https://mlsanity.com/paper/2307.13685/) (2023)

## Abstract (arXiv)

The k-means++ algorithm is a standard and widely used seeding method for k-means clustering, but for a fixed number k of centers its worst-case expected approximation ratio is Theta(log k). We consider the same algorithm when an adversary first fixes the dataset and some K; the number of centers k is then chosen uniformly from K,ldots,2K-1. We prove that k-means++ is an O(1)-approximation with constant probability in this budget-smoothed setup.