Adaptive Sampling for k-means Clustering


Amit Deshpande Microsoft Research Scientia, 196/36, 2nd Main, Sadashivnagar, Bangalore 560080


Friday, 25 September 2009 (All day)


  • A-212 (STCS Seminar Room)

k-means clustering is a theoretically hard problem but in practice it is often solved efficiently using a simple heuristic due to Lloyd. In this talk, we will modify Lloyd's method to get a simple, fast algorithm for k-means clustering with provable guarantee, i.e., constant factor approximation. Our algorithm is randomized and improves upon a previous result by Arthur and Vassilvitskii (joint work with Ankit Aggarwal and Ravindran Kannan.)