On clusterings good, bad and spectral. - Kannan, Ravi
We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have polylogarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.
Keywords: Theory of computation; Analysis of algorithms and problem complexity; Information systems; Information storage and retrieval; Algorithms; Theory