Timezone: »

 
Poster
Improved Guarantees for k-means++ and k-means++ Parallel
Konstantin Makarychev · Aravind Reddy · Liren Shan

Wed Dec 09 09:00 PM -- 11:00 PM (PST) @ Poster Session 4 #1178
in Poster Session 5 »

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