期刊
JOURNAL OF THE ACM
卷 51, 期 3, 页码 497-515出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/990308.990313
关键词
algorithms; theory; clustering; graph algorithms; spectral methods
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据