Jul 2026
Randomizing the Number of Centers in k-means++
It is proved that the k-means++ algorithm is an $O(1)$-approximation with constant probability in this budget-smoothed setup.
Václav Rozhon
· arXiv.org · 0 citations