The complexity of the \texttt{k-means} method

DOI10.4230/LIPICS.ESA.2016.78MaRDI QIDQ4606353zbMATH OpenOpenAlexFDO

Authors Tim Roughgarden, Joshua R. Wang

Publication date 2 March 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.ESA.2016.78

zbMATH Keywords

\(k\)-meansPSPACE-complete

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) 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
• k-means requires exponentially many iterations even in the plane
• Smoothed analysis of the k-means method
• How fast is the \(k\)-means method?
• How fast is the \(k\)-means method?

Cited in

(7)

• Complexity of single-swap heuristics for metric facility location and related problems
• An LP-based k-means algorithm for balancing weighted point sets
• scientific article; zbMATH DE number 1927359 (Why is no real title available?)
• 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
• Complexity of local search for Euclidean clustering problems

This page was built for publication: The complexity of the \texttt{k-means} method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606353)