Václav Rozhoň

2 accepted papers

2022

Adapting k-means Algorithms for Outliers

ICML 2022spotlight

This paper shows how to adapt several simple and classical sampling-based algorithms for the k-means problem to the setting with outliers. Recently, Bhaskara et al. (NeurIPS 2019) showed how to adapt the classical k-means++ algorithm to the setting with outliers. However, their algorithm needs to ou…

Cited by 10 Source ↗PDF ↗Scholar ↗

2020

Simple and sharp analysis of k-means||

Václav Rozhoň

ICML 2020poster

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.

Cited by 5 Source ↗PDF ↗Scholar ↗