Paper Info
Title
The Complexity of the k-means Method.
Abstract
The k-means method is a widely used technique for clustering points in Euclidean space. While it is extremely fast in practice, its worst-case running time is exponential in the number of data points. We prove that the k-means method can implicitly solve PSPACE-complete problems, providing a complexity-theoretic explanation for its worst-case running time. Our result parallels recent work on the complexity of the simplex method for linear programming.
Year
Venue
Field
2016
ESA
Data point,Discrete mathematics,k-means clustering,Parallels,Combinatorics,Exponential function,Simplex algorithm,Computer science,Euclidean space,Linear programming,Cluster analysis
DocType
Citations 
PageRank 
Conference
3
0.40
References 
Authors
0
2
Name
Order
Citations
PageRank
Tim Roughgarden14177353.32
Joshua R. Wang2695.83