School of Technology and Computer Science Seminars

k-means clustering, stability and outliers

by Amit Deshpande (Microsoft Research India, Bangalore)

Tuesday, March 19, 2019 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
Abstract: k-means is a popular clustering objective that is NP-hard in theory but often optimized efficiently in practice. Sampling-based algorithms such as k-means++ and approximation schemes give provable approximation guarantees for the worst-case instances of k-means. In this talk, we will discuss new results on how these algorithms perform for stable instances and in the presence of outliers. Based on joint works with (a) Anand Louis, Apoorv Vikram Singh (IISc) and (b) Praneeth Kacham (IIT Delhi), Rameshwar Pratap (IIIT Bangalore).