A Constant-Factor Bi-Criteria Approximation Guarantee for $k$-means++

Abstract

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 $\beta >1$, selecting $\beta 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 $\beta =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.

arXiv comment17 pages, 1 figure

References in corpus (1)

• A bi-criteria approximation algorithm for $k$ Means

Cited by in corpus (6)

• Improved Guarantees for k-means++ and k-means++ Parallel
• k-means++: few more steps yield constant approximation
• Noisy, Greedy and Not So Greedy k-means++
• Simple and sharp analysis of k-means||
• Balanced Districting on Grid Graphs with Provable Compactness and Contiguity
• Accurate MapReduce Algorithms for $k$-median and $k$-means in General Metric Spaces