Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces

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/ε)ᵈ⁻¹} ⋅ 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/εᵈ⁻¹) n^O(1) algorithm achieving a (1+ε)-approximation for k-means.