NP-hardness of Euclidean sum-of-squares clustering

被引：600

作者：

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

Beringer, Juergen ;

Huellermeier, Eyke .

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

Drineas, P ;

Frieze, A ;

Kannan, R ;

Vempala, S ;

Vinay, V .

MACHINE LEARNING, 2004, 56 (1-3) :9-33

[9] Cluster analysis and mathematical programming [J].

Hansen, P ;

Jaumard, B .

MATHEMATICAL PROGRAMMING, 1997, 79 (1-3) :191-215

[10]

KANADE G, 2008, NP HARDNESS 2 UNPUB

← 1 2 →