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ᵒ (1/ε^d-1) nO (1) algorithm achieving a (1+ε) -approximation for k-means.
Cohen-Addad et al. (Thu,) studied this question.