The planar k-means problem is NP-hard

被引：156

作者：

Mahajan, Meena ^{[1
]}

Nimbhorkar, Prajakta ^{[1
]}

Varadarajan, Kasturi ^{[2
]}

机构：

[1] Inst Math Sci, Madras 600113, Tamil Nadu, India

[2] Univ Iowa, Iowa City, IA 52242 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 442卷

关键词：

Clustering; k-means; Planar graphs; NP-hardness;

D O I：

10.1016/j.tcs.2010.05.034

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the k-means problem, we are given a finite set S of points in R-m, and integer k >= 1, and we want to find k points (centers) so as to minimize the sum of the square of the Euclidean distance of each point in S to its nearest center. We show that this well-known problem is NP-hard even for instances in the plane, answering an open question posed by Dasgupta (2007) [7]. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：13 / 21

页数：9

共 22 条

[1]

Allender E, 2005, LECT NOTES COMPUT SC, V3821, P238, DOI 10.1007/11590156_19

[2] NP-hardness of Euclidean sum-of-squares clustering [J].

Aloise, Daniel ;

Deshpande, Amit ;

Hansen, Pierre ;

Popat, Preyas .

MACHINE LEARNING, 2009, 75 (02) :245-248

[3]

[Anonymous], P ACM SIAM S DISCR A

[4]

[Anonymous], 1986, CBMS NSF REGIONAL C

[5]

[Anonymous], 2003, P 35 ANN ACM S THEOR, DOI [10.1145/780542.780550, DOI 10.1145/780542.780550]

[6] Polynomial time approximation schemes for euclidean TSP and other geometric problems [J].

Arora, S .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :2-11

[7]

Arthur D., 2006, P IEEE S FDN COMP SC

[8]

Arthur D., P S COMP GEOM

[9]

Dasgupta S., 2007, CS20070890 U CALIFOR

[10] 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

← 1 2 3 →