On clusterings - Good, bad and spectral

被引:105
作者
Kannan, R [1 ]
Vempala, S [1 ]
Vetta, A [1 ]
机构
[1] Yale Univ, New Haven, CT 06520 USA
来源
41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2000年
关键词
D O I
10.1109/SFCS.2000.892125
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 hy 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.
引用
收藏
页码:367 / 377
页数:11
相关论文
共 15 条
  • [1] [Anonymous], IEEE C COMP VIS PATT
  • [2] AZAR Y, UNPUB SPECTRAL ANAL
  • [3] Benczur A. A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P47, DOI 10.1145/237814.237827
  • [4] Charikar M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P1, DOI 10.1145/301250.301257
  • [5] CHARIKAR M, 1997, P 29 STOC
  • [6] DRINEAS P, 1999, P 10 SODA
  • [7] A SIMPLE HEURISTIC FOR THE P-CENTER PROBLEM
    DYER, ME
    FRIEZE, AM
    [J]. OPERATIONS RESEARCH LETTERS, 1985, 3 (06) : 285 - 288
  • [8] FRIEZE A, 1998, P 39 FOCS
  • [9] Indyk P., 1999, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), P154, DOI 10.1109/SFFCS.1999.814587
  • [10] JAIN K, 1999, P 40 ANN IEEE S FDN, P2