Center-based Clustering under Perturbation Stability

Pranjal Awasthi, Avrim Blum, Or Sheffet

Clustering under most popular objective functions is NP-hard, even to approximate well, and so unlikely to be efficiently solvable in the worst case. Recently, Bilu and Linial \cit…