Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means

Zachary Friggstad, Kamyar Khodamoradi, Mohammad R. Salavatipour

We investigate the complexity of solving stable or perturbation-resilient instances of $k$-Means and $k$-Median clustering in fixed dimension Euclidean metrics (more generally doub…