NeurIPS 2020poster34 citations
Improved Guarantees for k-means++ and k-means++ Parallel
Konstantin Makarychev, Aravind Reddy, Liren Shan
Abstract
In this paper, we study k-means++ and k-means||, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means||. Our results give a better theoretical justification for why these algorithms perform extremely well in practice.
BibTeX
@inproceedings{NEURIPS2020_ba304f38,
author = {Makarychev, Konstantin and Reddy, Aravind and Shan, Liren},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {16142--16152},
publisher = {Curran Associates, Inc.},
title = {Improved Guarantees for k-means++ and k-means++ Parallel},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/ba304f3809ed31d0ad97b5a2b5df2a39-Paper.pdf},
volume = {33},
year = {2020}
}