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

Computational aspects related to convexity (52B55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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

• \(k\)-means requires exponentially many iterations even in the plane
• k-means requires exponentially many iterations even in the plane
• A local search approximation algorithm for \(k\)-means clustering
• How fast is the \(k\)-means method?
• scientific article; zbMATH DE number 5506203 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• k-Means Has Polynomial Smoothed Complexity
• 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

Cited in

(29)

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

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)