Improved Guarantees for K-Means++ and K-Means++ Parallel

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.

PDF NeurIPS Semantic Scholar

Cite

Text

Makarychev et al. "Improved Guarantees for K-Means++ and K-Means++ Parallel." Neural Information Processing Systems, 2020.

Markdown

[Makarychev et al. "Improved Guarantees for K-Means++ and K-Means++ Parallel." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/makarychev2020neurips-improved/)

BibTeX

@inproceedings{makarychev2020neurips-improved,
  title     = {{Improved Guarantees for K-Means++ and K-Means++ Parallel}},
  author    = {Makarychev, Konstantin and Reddy, Aravind and Shan, Liren},
  booktitle = {Neural Information Processing Systems},
  year      = {2020},
  url       = {https://mlanthology.org/neurips/2020/makarychev2020neurips-improved/}
}