Improved Guarantees for k-means++ and k-means++ Parallel


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.

In Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
Click the Cite button above to demo the feature to enable visitors to import publication metadata into their reference management software.
Create your slides in Markdown - click the Slides button to check out the example.

Supplementary notes can be added here, including code, math, and images.

Aravind Reddy
Aravind Reddy
Postdoctoral Associate

My research interests include machine learning and computational biology.