k-Means Has Polynomial Smoothed Complexity.

David Arthur, Bodo Manthey, Heiko Rglin

Browse the full FOCS paper archive.