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