2026-07-22T16:58:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6419 2024-03-06T10:38:13Z ddc:004 open_access

The Complexity of the k-means Method Roughgarden, Tim Wang, Joshua R. k-means PSPACE-complete The k-means method is a widely used technique for clustering points in Euclidean space. While it is extremely fast in practice, its worst-case running time is exponential in the number of data points. We prove that the k-means method can implicitly solve PSPACE-complete problems, providing a complexity-theoretic explanation for its worst-case running time. Our result parallels recent work on the complexity of the simplex method for linear programming. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tim Roughgarden and Joshua R. Wang 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.78 urn:nbn:de:0030-drops-64191 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.78 eng https://creativecommons.org/licenses/by/3.0/legalcode