Recovery guarantees for exemplar-based clustering

Abhinav Nellore, Rachel Ward

For a certain class of distributions, we prove that the linear programming relaxation of $k$-medoids clustering---a variant of $k$-means clustering where means are replaced by exem…