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

Abstract

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+\epsilon )$-factor approximation in low-dimensional Euclidean metric for both the $k$-median and $k$-means problems in near-linear time $2^{(1/\epsilon {)}^{O(d^2)}}n\cdot \text{polylog}(n)$ (where $d$ is the dimension and $n$ is the number of input points). We improve this running time to $2^{\tilde{O}(1/\epsilon {)}^{d-1}}\cdot n\cdot \text{polylog}(n)$, and show an almost matching lower bound: under the Gap Exponential Time Hypothesis for 3-SAT, there is no $2^{o(1/{\epsilon }^{d-1})}{n}^{O(1)}$ algorithm achieving a $(1+\epsilon )$-approximation for $k$-means.