Name
Abstract | ||
|---|---|---|
In the k-means problem, we are given a finite set S of points in $\Re^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 [6]. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2010.05.034 | WALCOM '09 Proceedings of the 3rd International Workshop on Algorithms and Computation |
Keywords | DocType | Volume |
Euclidean distance,open question,nearest center,k-means problem,k point,well-known problem,finite set,planar k-means problem,integer k | Conference | 442, |
ISSN | Citations | PageRank |
Theoretical Computer Science | 109 | 3.95 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Prajakta Nimbhorkar | 2 | 170 | 15.04 |
| Kasturi Varadarajan | 3 | 1269 | 84.78 |