k-Means has Polynomial Smoothed Complexity

David Arthur, Bodo Manthey, Heiko Röglin

The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential wors…