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