A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions
Amit Kumar, Yogish Sabharwal, Subhankar Sen · 2004
We present the first linear time (1 + /spl epsiv/)-approximation algorithm for the k-means problem for fixed k and /spl epsiv/. 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.