Tata Institute of Fundamental Research
k-means clustering, stability and outliers
STCS Seminar
Speaker:
Amit Deshpande (Microsoft Research India
Bangalore)
Organiser:
Prahladh Harsha
Date:
Tuesday, 19 Mar 2019, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Amit Deshpande (Microsoft Research India Bangalore) |
| Organiser: | Prahladh Harsha |
| Date: | Tuesday, 19 Mar 2019, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).