Journal article
The planar k-means problem is NP-hard
Theoretical computer science, Vol.442, pp.13-21
07/13/2012
DOI: 10.1016/j.tcs.2010.05.034
Abstract
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.
Details
- Title: Subtitle
- The planar k-means problem is NP-hard
- Creators
- Meena Mahajan - Institute of Mathematical SciencesPrajakta Nimbhorkar - Institute of Mathematical SciencesKasturi Varadarajan - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Theoretical computer science, Vol.442, pp.13-21
- DOI
- 10.1016/j.tcs.2010.05.034
- ISSN
- 0304-3975
- eISSN
- 1879-2294
- Publisher
- Elsevier
- Number of pages
- 9
- Language
- English
- Date published
- 07/13/2012
- Academic Unit
- Computer Science
- Record Identifier
- 9984259470702771
Metrics
119 Record Views