Near-Linear Time Approximation Algorithms for k-means with Outliers

We present the first linear time (1 + ε)-approximation algorithm for the k-means problem for fixed k and ε. 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.