Journal
THEORETICAL COMPUTER SCIENCE
Volume 442, Issue -, Pages 13-21Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2010.05.034
Keywords
Clustering; k-means; Planar graphs; NP-hardness
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available