A Constant-Factor Bi-Criteria Approximation Guarantee for $k$-means++
This provides a theoretical guarantee for clustering algorithms, improving upon prior results that were weaker or probabilistic, which is incremental but useful for algorithm design and analysis.
The paper tackles the problem of approximating optimal k-means clustering by showing that selecting βk centers using D^ℓ sampling yields a constant-factor approximation in expectation, extending previous O(log k) guarantees to a constant-factor bi-criteria regime.
This paper studies the $k$-means++ algorithm for clustering as well as the class of $D^\ell$ sampling algorithms to which $k$-means++ belongs. It is shown that for any constant factor $β> 1$, selecting $βk$ cluster centers by $D^\ell$ sampling yields a constant-factor approximation to the optimal clustering with $k$ centers, in expectation and without conditions on the dataset. This result extends the previously known $O(\log k)$ guarantee for the case $β= 1$ to the constant-factor bi-criteria regime. It also improves upon an existing constant-factor bi-criteria result that holds only with constant probability.