Timezone: »

 
Poster
A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++
Dennis Wei

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #24
in Tuesday Posters »
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.
Keywords: Clustering · Combinatorial Optimization · (Other) Optimization
[ PDF] 

Author Information

Dennis Wei (IBM Research)

More from the Same Authors