Mahajan, Meena ; Nimbhorkar, Prajakta ; Varadarajan, Kasturi (2012) The planar k-means problem is NP-hard Theoretical Computer Science, 442 . pp. 13-21. ISSN 0304-3975
![[img]](https://repository.ias.ac.in/style/images/fileicons/application_pdf.png) |
PDF
289kB |
Official URL: http://doi.org/10.1016/j.tcs.2010.05.034
Related URL: http://dx.doi.org/10.1016/j.tcs.2010.05.034
Abstract
In the k-means problem, we are given a finite set S of points in ℜ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].
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier B.V. |
| Keywords: | Clusteringk-means; Planar graphs; NP-hardness |
| ID Code: | 128048 |
| Deposited On: | 14 Oct 2022 11:24 |
| Last Modified: | 14 Oct 2022 11:24 |
Repository Staff Only: item control page
