Simple and sharp analysis of k-means||
arXiv:2003.02518
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 to , which we show to be tight.
References in corpus (6)
- A Comparative Study of Efficient Initialization Methods for the K-Means Clustering Algorithm
- Tight Bounds for Parallel Randomized Load Balancing
- A Constant-Factor Bi-Criteria Approximation Guarantee for -means++
- Noisy, Greedy and Not So Greedy k-means++
- A simple D^2-sampling based PTAS for k-means and other Clustering Problems
- Optimal Time Bounds for Approximate Clustering