Randomizing the Number of Centers in k-means++
Vaclav Rozhon
cs.DS, cs.LG, stat.ML
Submitted: 2026-07-28
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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 (k).
Terminology
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 (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,,2K-1. We prove that k-means++ is an O(1) -approximation with constant probability in this budget-smoothed setup.
Related papers
- Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
- Computational and Statistical Hardness of Calibration Distance
- Edge-Private Matching Kernels Through Local Decoding
- Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
- Local Node Differential Privacy
- Cheaper by the Batch: Shared Traversal for Genotype Graph Editing