The uniqueness of a good optimum for K-means

If we have found a ”good ” clustering C of a data set, can we prove that C is not far from the (unknown) best clustering Copt of these data? Perhaps surprisingly, the answer to this question is sometimes yes. When “goodness ” is measured by the distortion of K-means clustering, this paper proves spectral bounds on the distance d(C, Copt). The bounds exist in the case when the data admits a low distortion clustering. 1.