Simple and sharp analysis of k-means||

Abstract

We present a simple analysis of k-means|| (Bahmani et al., PVLDB 2012) -- a distributed variant of the k-means++ algorithm (Arthur and Vassilvitskii, SODA 2007). Moreover, the bound on the number of rounds is improved from $O(\log n)$ to $O(\log n/\log \log n)$, which we show to be tight.

References in corpus (4)

• A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm
• Tight Bounds for Parallel Randomized Load Balancing
• Noisy, Greedy and Not So Greedy k-means++
• Optimal Time Bounds for Approximate Clustering