ICML 2020poster6 citations
k-means++: few more steps yield constant approximation
Davin Choo, Christoph Grunau, Julian Portmann, Vaclav Rozhon
Abstract
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 yield a constant approximation (in expectation) to the k-means clustering problem. In this paper, we improve their analysis to show that, for any arbitrarily small constant epsilon > 0, with only epsilon * k additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper.
BibTeX
@InProceedings{pmlr-v119-choo20a,
title = {k-means++: few more steps yield constant approximation},
author = {Choo, Davin and Grunau, Christoph and Portmann, Julian and Rozhon, Vaclav},
booktitle = {Proceedings of the 37th International Conference on Machine Learning},
pages = {1909--1917},
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/choo20a/choo20a.pdf},
url = {https://proceedings.mlr.press/v119/choo20a.html},
abstract = {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 yield a constant approximation (in expectation) to the k-means clustering problem. In this paper, we improve their analysis to show that, for any arbitrarily small constant epsilon > 0, with only epsilon * k additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper.}
}