The planar k-means problem is NP-hard
The planar k-means problem is NP-hard
复制标题
DOI：
10.1016/j.tcs.2010.05.034
复制
发表时间：
2012-07-13
影响因子：
1.1
通讯作者：
Varadarajan, Kasturi
中科院分区：
文献类型：
--
作者：
Mahajan, Meena;Nimbhorkar, Prajakta;Varadarajan, Kasturi
在k-均值问题中，我们给定R-m中的有限点集S，整数k >= 1，我们希望找到k个点（中心），以便最小化S中每个点到其最近中心的欧氏距离的平方和。我们证明了这个著名的问题即使在平面上也是NP难的，回答了Dasgupta（2007）[7]提出的一个开放问题。(C)2010 Elsevier B. V.保留所有权利。
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.