Polynomial Time Algorithm for $2$-Stable Clustering Instances

Ainesh Bakshi, Nadiia Chepurko

Clustering with most objective functions is NP-Hard, even to approximate well in the worst case. Recently, there has been work on exploring different notions of stability which len…