ICML 2020poster5 citations
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.
BibTeX
@InProceedings{pmlr-v119-rozhon20a,
title = {Simple and sharp analysis of k-means||},
author = {Rozho{\v{n}}, V{\'a}clav},
booktitle = {Proceedings of the 37th International Conference on Machine Learning},
pages = {8266--8275},
year = {2020},
editor = {III, Hal Daumé and Singh, Aarti},
volume = {119},
series = {Proceedings of Machine Learning Research},
month = {13--18 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v119/rozhon20a/rozhon20a.pdf},
url = {https://proceedings.mlr.press/v119/rozhon20a.html},
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.}
}