An Analysis of $D^{\alpha }$ seeding for $k$-means

Etienne Bamas, Sai Ganesh Nagarajan, Ola Svensson

One of the most popular clustering algorithms is the celebrated $D^{\alpha }$ seeding algorithm (also know as $k$-means++ when $\alpha =2$) by Arthur and Vassilvitskii (2007), who showed that it…