Christoph Grunau

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

k-means++: few more steps yield constant approximation

Davin Choo, Christoph Grunau, Julian Portmann, Vaclav Rozhon

ICML 2020poster

The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k) approximation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to…

Cited by 6 Source ↗PDF ↗Scholar ↗