Timezone: »
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.
Author Information
Konstantin Makarychev (Northwestern University)
Aravind Reddy (Northwestern University)
Aravind is a third-year PhD student at Northwestern University in the CS theory group advised by Prof. Konstantin Makarychev and Prof. Aravindan Vijayaraghavan. Before joining Northwestern, he was an undergrad at Indian Institute of Technology Kanpur where he majored in Computer Science and Engineering, and minored in Physics. He is broadly interested in theoretical computer science and is currently working on projects related to Approximation algorithms and Theoretical machine learning.
Liren Shan (Northwestern University)
More from the Same Authors
-
2022 Poster: Dynamic Tensor Product Regression »
Aravind Reddy · Zhao Song · Lichen Zhang -
2019 Poster: Correlation clustering with local objectives »
Sanchit Kalhan · Konstantin Makarychev · Timothy Zhou -
2017 Poster: Clustering Billions of Reads for DNA Data Storage »
Cyrus Rashtchian · Konstantin Makarychev · Miklos Racz · Siena Ang · Djordje Jevdjic · Sergey Yekhanin · Luis Ceze · Karin Strauss -
2017 Spotlight: Clustering Billions of Reads for DNA Data Storage »
Cyrus Rashtchian · Konstantin Makarychev · Miklos Racz · Siena Ang · Djordje Jevdjic · Sergey Yekhanin · Luis Ceze · Karin Strauss