The planar<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>k</mml:mi></mml:math>-means problem is NP-hard
Theoretical Computer SciencePublished 11 June 2010
Meena Mahajan, Prajakta Nimbhorkar, Kasturi Varadarajan
Citations281
SJR quartileQ2
SJR score0.49
SNIP0.94
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
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].
Keywords
Computer Science
IEEE Transactions on Information TheoryLeast squares quantization in PCM
15,578 Citations1982Sheelagh Lloyd
The corresponding result for any finite number of quanta is derived; that is, necessary conditions are found that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.
k-means++: the advantages of careful seeding
6,303 Citations2007David Arthur, Sergei Vassilvitskii
By augmenting k-means with a very simple, randomized seeding technique, this work obtains an algorithm that is Θ(logk)-competitive with the optimal clustering.
Machine LearningNP-hardness of Euclidean sum-of-squares clustering
863 Citations2009Daniel Aloise, Amit Deshpande +2 more
A recent proof of NP-hardness of Euclidean sum-of-squares clustering, due to Drineas et al. (Mach. 56:9–33, 2004), is not valid and an alternate short proof is provided.
SIAM Journal on ComputingPlanar Formulae and Their Uses
746 Citations1982David Lichtenstein
Using these results, it is able to provide simple and nearly uniform proofs of NP-completeness for planar node cover, planar Hamiltonian circuit and line, geometric connected dominating set, and of polynomial space completeness forPlanar generalized geography.
SIAM Journal on ComputingOn the Complexity of Some Common Geometric Location Problems
665 Citations1984Nimrod Megiddo, Kenneth J. Supowit
The p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard and the reductions are from 3-satisfiability.
A local search approximation algorithm for k-means clustering
497 Citations2002Tapas Kanungo, David M. Mount +4 more
This work considers the question of whether there exists a simple and practical approximation algorithm for k-means clustering, and presents a local improvement heuristic based on swapping centers in and out that yields a (9+ε)-approximation algorithm.
Machine LearningClustering Large Graphs via the Singular Value Decomposition
477 Citations2004Petros Drineas, Alan Frieze +3 more
This paper considers the problem of partitioning a set of m points in the n-dimensional Euclidean space into k clusters, and considers a continuous relaxation of this discrete problem: find the k-dimensional subspace V that minimizes the sum of squared distances to V of the m points, and argues that the relaxation provides a generalized clustering which is useful in its own right.
Polynomial time approximation schemes for Euclidean TSP and other geometric problems
446 Citations2002Sanjeev Arora
A polynomial time approximation scheme for Euclidean TSP in /spl Rfr//sup 2/ that finds a (1+/spl epsiv/)-approximation to the optimum traveling salesman tour in time n/sup 0(1//spl ePSiv/)/.
IEEE Transactions on ComputersUniversality considerations in VLSI circuits
389 Citations1981Leslie G. Valiant
The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed and restricted classes of graphs have to be considered in order to achieve compact embeddings.
Society for Industrial and Applied Mathematics eBooksAn Algorithmic Theory of Numbers, Graphs and Convexity
354 Citations1986László Lovász
How to Round Numbers Preliminaries and some Applications in Combinatorics Cuts and Joins Chromatic Number, Cliques and Perfect Graphs Minimizing a Submodular Function.
Applications of weighted Voronoi diagrams and randomization to variance-based <i>k</i>-clustering
321 Citations1994Mary Inaba, Naoki Katoh +1 more
The optimum solution to the k-clustering problem is characterized by the ordinary Euclidean Voronoi diagram and the weighted Vor onoi diagram with both multiplicative and additive weights.
How slow is the <i>k</i> -means method?
307 Citations2006David Arthur, Sergei Vassilvitskii
It is demonstrated that the worst-case running time of the k-means method is superpolynomial by improving the best known lower bound from Ω(n) iterations to 2Ω(√n).
Computational GeometryA local search approximation algorithm for k-means clustering
291 Citations2004Tapas Kanungo, David M. Mount +4 more
The Effectiveness of Lloyd-Type Methods for the k-Means Problem
265 Citations2006Rafail Ostrovsky, Yuval Rabani +2 more
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Area-Efficient Graph Layouts (for VLSI).
254 Citations1980Charles E. Leiserson
An algorithm is given that produces VLSI layouts for classes of graphs that have good separator theorems and shows in particular that any planar graph of n vertices has an O(n lg-square(n) area layout and that any tree of n Vertices can be laid out in linear area.
A Simple Linear Time (1+ &#8714;) -Approximation Algorithm for k-Means Clustering in Any Dimensions
242 Citations2004Amit Kumar, Yogish Sabharwal +1 more
This work presents the first linear time (1 + /spl epsiv/)-approximation algorithm for the k-means problem for fixed k and /spl Epsiv/, which runs in O(nd) time.
The hardness of k-means clustering
166 Citations2008Sanjoy Dasgupta
Approximation schemes for clustering problems
158 Citations2003W. Fernandez de la Véga, Marek Karpiński +2 more
The first polynomial time approximation schemes for clustering problems are given, and the running time of the algorithms is a vast improvement overprevious work.
Area-efficient graph layouts
152 Citations1980Charles E. Leiserson
An algorithm is given that produces VLSI layouts for classes of graphs that have good separator theorems, and it is shown that any planar graph of n vertices has an O(n lg2 n) area layout and that any tree of n Vertices can be laid out in linear area.
Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method
60 Citations2006David Arthur, Sergei Vassilvitskii
Symposium on Discrete AlgorithmsHow fast is the k-means method?
46 Citations2005Sariel Har-Peled, Bardia Sadri
Lecture notes in computer scienceThe Directed Planar Reachability Problem
30 Citations2005Eric Allender, Samir Datta +1 more
The s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete, is investigated and it is shown that this problem is logspace-reducible to its complement and the problem of searching graphs of genus 1 reduces to the planar case.
AlgorithmicaOn Metric Clustering to Minimize the Sum of Radii
26 Citations2009Matt Gibson, Gaurav Kanade +3 more
A randomized algorithm that runs in nO(log n⋅logΔ) time and returns with high probability the optimal solution to the problem of covering P by k balls so as to minimize the sum of the radii of the balls.
Symposium on Discrete AlgorithmsOn clustering to minimize the sum of radii
24 Citations2008Matt Gibson, Gaurav Kanade +3 more