Randomizing the Number of Centers in k-means++

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 Θ(\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.