NP-hardness of Euclidean sum-of-squares clustering

被引：584

作者：

Aloise, Daniel ^{[1
]}

Deshpande, Amit ^{[2
]}

Hansen, Pierre ^{[3
,4
]}

Popat, Preyas ^{[5
]}

机构：

[1] Ecole Polytech, Montreal, PQ H3C 3A7, Canada

[2] Microsoft Res India, Bangalore 560080, Karnataka, India

[3] Gerad, Montreal, PQ H3T 2A7, Canada

[4] HEC Montreal, Montreal, PQ H3T 2A7, Canada

[5] Chennai Math Inst, Siruseri 603103, India

来源：

MACHINE LEARNING | 2009年 / 75卷 / 02期

关键词：

Clustering; Sum-of-squares; Complexity; GRAPHS;

D O I：

10.1007/s10994-009-5103-0

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

A recent proof of NP-hardness of Euclidean sum-of-squares clustering, due to Drineas et al. (Mach. Learn. 56:9-33, 2004), is not valid. An alternate short proof is provided.

引用

页码：245 / 248

页数：4

共 12 条

[1] ALOISE D, 2007, G200750 GERAD
[2] [Anonymous], P 5 BERK S MATH STAT
[3] ARTHUR D., 2007, 2007 ACM SIAM S DISC
[4] Online clustering of parallel data streams
Beringer, Juergen
Huellermeier, Eyke
[J]. DATA & KNOWLEDGE ENGINEERING, 2006, 58 (02) : 180 - 204
[5] Cilibrasi R, 2005, LECT NOTES COMPUT SC, V3692, P128
[6] Dasgupta S., 2008, Technical Report CS2008-0916
[7] DESHPANDE A, 2008, COMMUNICATION 0122
[8] Clustering large graphs via the Singular Value Decomposition
Drineas, P
Frieze, A
Kannan, R
Vempala, S
Vinay, V
[J]. MACHINE LEARNING, 2004, 56 (1-3) : 9 - 33
[9] Cluster analysis and mathematical programming
Hansen, P
Jaumard, B
[J]. MATHEMATICAL PROGRAMMING, 1997, 79 (1-3) : 191 - 215
[10] KANADE G, 2008, NP HARDNESS 2 UNPUB

← 1 2 →