k-means requires exponentially many iterations even in the plane
DOI10.1007/S00454-011-9340-1zbMATH Open1218.68088OpenAlexW2950437976WikidataQ56480221 ScholiaQ56480221MaRDI QIDQ540436FDOQ540436
Authors: Andrea Vattani 
Publication date: 3 June 2011
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-011-9340-1
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects related to convexity (52B55)
Cites Work
- Least squares quantization in PCM
- Title not available (Why is that?)
- k-Means Has Polynomial Smoothed Complexity
- Title not available (Why is that?)
- \(k\)-means requires exponentially many iterations even in the plane
- \(k\)-means requires exponentially many iterations even in the plane
- Smoothed analysis of algorithms
- Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
- A local search approximation algorithm for \(k\)-means clustering
- How fast is the \(k\)-means method?
- Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences
Cited In (27)
- An efficient \(K\)-means clustering algorithm for tall data
- On the Complexity of Clustering with Relaxed Size Constraints
- A refined approximation for Euclidean \(k\)-means
- A bad instance for \texttt{k-means++}
- The seeding algorithm for spherical \(k\)-means clustering with penalties
- When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
- On the minimum of the mean-squared error in 2-means clustering
- \(k\)-means requires exponentially many iterations even in the plane
- Exact algorithms for size constrained 2-clustering in the plane
- \(k\)-means requires exponentially many iterations even in the plane
- The complexity of the \texttt{k-means} method
- How fast is the \(k\)-means method?
- The Planar k-Means Problem is NP-Hard
- Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
- Fast indefinite multi-point (IMP) clustering
- A bad instance for \(k\)-means++
- On the complexity of clustering with relaxed size constraints in fixed dimension
- Iterative ensemble normalized cuts
- Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
- How fast is the \(k\)-means method?
- Good clusterings have large volume
- An LP-based \(k\)-means algorithm for balancing weighted point sets
- Local Search Yields a PTAS for $k$-Means in Doubling Metrics
- An approximation algorithm for the uniform capacitated \(k\)-means problem
- Construction of the similarity matrix for the spectral clustering method: numerical experiments
- Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
- Also for \(k\)-means: more data does not imply better performance
Uses Software
This page was built for publication: \(k\)-means requires exponentially many iterations even in the plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540436)
