arXiv Open Access 2020

Simple and sharp analysis of k-means||

Václav Rozhoň

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS

Penulis (1)

Václav Rozhoň

Format Sitasi

APA MLA BibTeX

Rozhoň, V. (2020). Simple and sharp analysis of k-means||. https://arxiv.org/abs/2003.02518

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓