Reviews: How to tell when a clustering is (approximately) correct using convex relaxations

This paper presents a general method to derive bounds on how close a given clustering is to an optimal clustering where optimal is defined according to certain loss functions. The method can be used for any clustering loss function for which convex relaxation exists (e.g., K-means, spectral clustering). They show in experiments they obtain much better bounds than the only related work (as far as I know) on K-means [Mei06]. The paper is well-written and easy to follow and addresses an important problem of evaluating the quality of clusterings. The main contribution of the paper is to make use of tighter convex relaxations to derive bounds on the distance between optimal clustering and a given clustering.