k-means clustering

I will present a recent remarkable algorithm by Kumar, Sabharwal and Sen 
for k-means clustering.  given a set of points P, the problem is to find a 
set K of k centers, such that the sum of the squared distance from each 
point in P to its nearest neighbor in K is minimized.  They give a 
(1+eps)-approximation algorithm for this problem with running time bounded 
by O(nd), where n is the number of points in P and d is the dimension.