On clusterings good, bad and spectral.

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...

Ausführliche Beschreibung

Bibliographische Detailangaben

Veröffentlicht in:	Journal of the ACM 51, 3 (2004).
1. Verfasser:	Kannan, Ravi
Format:	Artikel
Sprache:	English
Schlagworte:	Theory of computation. Analysis of algorithms and problem complexity. Information systems. Information storage and retrieval. Algorithms. Theory.