Research
Randomizing the Number of Centers in k-means++
arXiv:2607.26202v1 Announce Type: cross Abstract: 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 expect
arXiv:2607.26202v1 Announce Type: cross Abstract: 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.
Source: arXiv cs.LG | 2026-07-30