2026-09-05T11:58:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25839 2026-06-23T12:59:19Z ddc:004 open_access

Near-Optimal Bounds for Parameterized Euclidean k-Means Cohen-Addad, Vincent C. S., Karthik Saulpic, David Schwiegelshohn, Chris k-means clustering Euclidean space Fine-Grained Complexity The k-means problem is a classic objective for modeling clustering in a metric space. Given a set of points in a metric space, the goal is to find k representative points so as to minimize the sum of the squared distances from each point to its closest representative. In this work, we study the approximability of k-means in Euclidean spaces parameterized by the number of clusters, k. In seminal works, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] showed how to obtain a (1+ε)-approximation for high-dimensional Euclidean k-means in time 2^{(k/ε)^O(1)} ⋅ dn^O(1). In this work, we introduce a new fine-grained hypothesis called Exponential Time for Expanders Hypothesis (XXH) which roughly asserts that there are no non-trivial exponential time approximation algorithms for the vertex cover problem on near perfect vertex expanders. Assuming XXH, we close the above long line of work on approximating Euclidean k-means by showing that there is no 2^{(k/ε)^{1-o(1)}} ⋅ n^O(1) time algorithm achieving a (1+ε)-approximation for k-means in Euclidean space. This lower bound is tight as it matches the algorithm given by Feldman, Monemizadeh, and Sohler [SoCG'07] whose runtime is 2^O(k/ε) + O(ndk). Furthermore, assuming XXH, we show that the seminal O(n^{kd+1}) runtime exact algorithm of Inaba, Katoh, and Imai [SoCG'94] for k-means is optimal for small values of k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincent Cohen-Addad and Karthik C. S. and David Saulpic and Chris Schwiegelshohn 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.33 urn:nbn:de:0030-drops-258391 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.33 eng https://creativecommons.org/licenses/by/4.0/legalcode