A Faster $k$-means++ Algorithm

Understand

$k$-means++ is an important algorithm for choosing initial cluster centers for the $k$-means clustering algorithm.

• In this work, we present a new algorithm that can solve the $k$-means++ problem with nearly optimal running time.
• Given $n$ data points in $\mathbb{R}^d$, the current state-of-the-art algorithm runs in $\widetilde{O}(k )$ iterations, and each iteration takes $\widetilde{O}(nd k)$ time.
• The overall running time is thus $\widetilde{O}(n d k^2)$.