On clusterings - Good, bad and spectral

被引：106

作者：

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 [J].

DYER, ME ;

FRIEZE, AM .

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

← 1 2 →