mlsanityData to 14 Oct 2026

Randomizing the Number of Centers in k-means++

arXiv 2607.26202 ↗First posted 28 Jul 2026cs.DS cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

10 of 23 references.

References · 10

  1. 2020k-means++: few more steps yield constant approximationcited by 16
  2. 2020Improved Guarantees for k-means++ and k-means++ Parallelcited by 12
  3. 2016A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++cited by 8
  4. 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
  5. 2020Adapting k-means algorithms for outlierscited by 6
  6. 2019Noisy, Greedy and Not So Greedy k-means++cited by 4
  7. 2021Budget-Smoothed Analysis for Submodular Maximizationcited by 3
  8. 2020Simple and sharp analysis of k-means||cited by 2
  9. 2022Beyond Worst-Case Budget-Feasible Mechanism Designcited by 1
  10. 2023Noisy k-means++ Revisitedcited by 1

Built on by

Not cited yet.