A simple linear time ( 1+ ε)- approximation algorithm for geometric k-means clustering in any dimensions
Amit Kumar, Yogish Sabharwal, Sandeep Sen · 2004
We present the first linear time (1+e)-approximation algorithm for the k-means problem for fixed k and e. Our algorithm runs in O(nd) time, which is linear in the size of the input. Another feature of our algorithm is its simplicity - the only technique involved is random sampling.