On Euclidean $k$-Means Clustering with $\alpha$-Center Proximity

Amit Deshpande, Anand Louis, Apoorv Vikram Singh

$k$-means clustering is NP-hard in the worst case but previous work has shown efficient algorithms assuming the optimal $k$-means clusters are \emph{stable} under additive or multi…