2026-07-20T07:52:45Z https://drops.dagstuhl.de/oai

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

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces Cohen-Addad, Vincent Karthik C. S. Saulpic, David Schwiegelshohn, Chris k-means clustering k-median clustering Euclidean space Fine-Grained Complexity The k-median and k-means clustering objectives are classic objectives for modeling clustering in a metric space. Given a set of points in a metric space, the goal of the k-median (resp. k-means) problem is to find k representative points so as to minimize the sum of the distances (resp. sum of squared distances) from each point to its closest representative. Cohen-Addad, Feldmann, and Saulpic [JACM'21] showed how to obtain a (1+ε)-factor approximation in low-dimensional Euclidean metric for both the k-median and k-means problems in near-linear time 2^{(1/ε)^O(d²)} n ⋅ polylog(n) (where d is the dimension and n is the number of input points). We improve this running time to 2^{O(1/ε)^{d-1}} ⋅ n ⋅ polylog(n), and show an almost matching lower bound: under the Gap Exponential Time Hypothesis for 3-SAT, there is no 2^o(1/ε^{d-1}) n^O(1) algorithm achieving a (1+ε)-approximation for k-means. 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.34 urn:nbn:de:0030-drops-258404 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.34 eng https://creativecommons.org/licenses/by/4.0/legalcode