Simple and sharp analysis of k-means||
Not on the map. Why?
Abstract (arXiv)
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 / loglog n), which we show to be tight.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Mar 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2022: 1; 2023: 0; 2024: 0; 2025: 0; 2026: 1.
2 papers.
- 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
- 2026Randomizing the Number of Centers in k-means++cited by 0
- 2026Randomizing the Number of Centers in k-means++28 Jul 2026
- 2022A Nearly Tight Analysis of Greedy k-means++16 Jul 2022