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

Davin Choo, Christoph Grunau, Julian Portmann, Vaclav Rozhon
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:1909-1917, 2020.

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.

Cite this 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.} }
Endnote
%0 Conference Paper %T k-means++: few more steps yield constant approximation %A Davin Choo %A Christoph Grunau %A Julian Portmann %A Vaclav Rozhon %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-choo20a %I PMLR %P 1909--1917 %U https://proceedings.mlr.press/v119/choo20a.html %V 119 %X 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.
APA
Choo, D., Grunau, C., Portmann, J. & Rozhon, V.. (2020). k-means++: few more steps yield constant approximation. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:1909-1917 Available from https://proceedings.mlr.press/v119/choo20a.html.

Related Material