The Complexity of the k-means Method

DOI10.4230/LIPIcs.ESA.2016.78zbMath1397.68108OpenAlexW2539040520MaRDI QIDQ4606353

Joshua R. Wang, Tim Roughgarden

Publication date: 2 March 2018

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

zbMATH Keywords

PSPACE-complete\(k\)-means

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems, Complexity of single-swap heuristics for metric facility location and related problems, An LP-based \(k\)-means algorithm for balancing weighted point sets