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).
