k-means requires exponentially many iterations even in the plane

DOI10.1007/S00454-011-9340-1MaRDI QIDQ540436zbMATH OpenOpenAlexWikidataFDO

Authors Andrea Vattani

Publication date 3 June 2011

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00454-011-9340-1

zbMATH Keywords

\(k\)-meanslocal searchlower bounds

Mathematics Subject Classification ID

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)

Recommendations

• \(k\)-means requires exponentially many iterations even in the plane
• How fast is the \(k\)-means method?
• How fast is the \(k\)-means method?
• The complexity of the \texttt{k-means} method
• Improved smoothed analysis of the \(k\)-means method

Cites work

• scientific article; zbMATH DE number 5506203 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• A local search approximation algorithm for \(k\)-means clustering
• How fast is the \(k\)-means method?
• Least squares quantization in PCM
• Smoothed analysis of algorithms
• Worst-case and smoothed analysis of \(k\)-means clustering with Bregman divergences
• Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
• \(k\)-means requires exponentially many iterations even in the plane
• \(k\)-means requires exponentially many iterations even in the plane
• k-Means Has Polynomial Smoothed Complexity

Cited in

(27)

• How fast is the \(k\)-means method?
• Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method
• \(k\)-means requires exponentially many iterations even in the plane
• The Planar k-Means Problem is NP-Hard
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
• A bad instance for \texttt{k-means++}
• Fast indefinite multi-point (IMP) clustering
• Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms
• How fast is the \(k\)-means method?
• An LP-based \(k\)-means algorithm for balancing weighted point sets
• The complexity of the \texttt{k-means} method
• On the minimum of the mean-squared error in 2-means clustering
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Exact algorithms for size constrained 2-clustering in the plane
• \(k\)-means requires exponentially many iterations even in the plane
• An efficient \(K\)-means clustering algorithm for tall data
• An approximation algorithm for the uniform capacitated \(k\)-means problem
• On the Complexity of Clustering with Relaxed Size Constraints
• The seeding algorithm for spherical \(k\)-means clustering with penalties
• On the complexity of clustering with relaxed size constraints in fixed dimension
• When do birds of a feather flock together? \(k\)-means, proximity, and conic programming
• A bad instance for \(k\)-means++
• A refined approximation for Euclidean \(k\)-means
• Also for \(k\)-means: more data does not imply better performance
• Construction of the similarity matrix for the spectral clustering method: numerical experiments
• Iterative ensemble normalized cuts
• Good clusterings have large volume

Describes a project that uses

Uses Software

• k-means++

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)