Clustering Stable Instances of Euclidean k-means

Abhratanu Dutta, Aravindan Vijayaraghavan, Alex Wang

The Euclidean k-means problem is arguably the most widely-studied clustering problem in machine learning. While the k-means objective is NP-hard in the worst-case, practitioners ha…