%0 Conference Paper %1 Kannan00spectralClustering %A Kannan, R. %A Vempala, S. %A Veta, A. %B FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science %C Washington, DC, USA %D 2000 %I IEEE Computer Society %K 00 Kannan clustering graph min-cut spectral %P 367 %T On clusterings-good, bad and spectral %U http://portal.acm.org/citation.cfm?id=796585 %X We propose a new measure for assessing the quality of a clustering. A simple heuristic is shown to give worst-case guarantees under the new measure. Then we present two results regarding the quality of the clustering found by a popular spectral algorithm. One proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it. %@ 0-7695-0850-2

@inproceedings{Kannan00spectralClustering, abstract = {We propose a new measure for assessing the quality of a clustering. A simple heuristic is shown to give worst-case guarantees under the new measure. Then we present two results regarding the quality of the clustering found by a popular spectral algorithm. One proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.}, added-at = {2008-10-27T21:09:42.000+0100}, address = {Washington, DC, USA}, author = {Kannan, R. and Vempala, S. and Veta, A.}, biburl = {https://www.bibsonomy.org/bibtex/20f31fefe3afd78c65dc60af5c61abf4a/lee_peck}, booktitle = {FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science}, description = {On clusterings-good, bad and spectral}, interhash = {83013716cf7b8dfb1fdc352172cff85d}, intrahash = {0f31fefe3afd78c65dc60af5c61abf4a}, isbn = {0-7695-0850-2}, keywords = {00 Kannan clustering graph min-cut spectral}, pages = 367, publisher = {IEEE Computer Society}, timestamp = {2009-02-02T16:44:16.000+0100}, title = {On clusterings-good, bad and spectral}, url = {http://portal.acm.org/citation.cfm?id=796585}, year = 2000 }