Book chapter
The Planar k-Means Problem is NP-Hard
WALCOM: Algorithms and Computation, pp.274-285
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2009
DOI: 10.1007/978-3-642-00202-1_24
Abstract
In the k-means problem, we are given a finite set S of points in \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\Re^m$\end{document}, 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].
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
- Book chapter
- Publication Details
- WALCOM: Algorithms and Computation, pp.274-285
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-642-00202-1_24
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2009
- Academic Unit
- Computer Science
- Record Identifier
- 9984259470502771
Metrics
9 Record Views