On clusterings: Good, bad and spectral Export

@article{citeulike:912649, abstract = {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 poly-logarithmic 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.}, address = {New York, NY, USA}, author = {Kannan, Ravi and Vempala, Santosh and Vetta, Adrian}, citeulike-article-id = {912649}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=990313}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/990308.990313}, doi = {10.1145/990308.990313}, issn = {0004-5411}, journal = {J. ACM}, month = {May}, number = {3}, pages = {497--515}, posted-at = {2006-10-25 20:13:48}, priority = {2}, publisher = {ACM}, title = {On clusterings: Good, bad and spectral}, url = {http://dx.doi.org/10.1145/990308.990313}, volume = {51}, year = {2004} }

TY - JOUR ID - citeulike:912649 L3 - citeulike-article-id:912649 N2 - 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 poly-logarithmic 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. IS - 3 JF - J. ACM SN - 0004-5411 AD - New York, NY, USA EP - 515 TI - On clusterings: Good, bad and spectral PB - ACM VL - 51 SP - 497 AU - Kannan, Ravi AU - Vempala, Santosh AU - Vetta, Adrian PY - 2004/05// UR - http://dx.doi.org/10.1145/990308.990313 ER -