What does this research mean for the field?

A (1+ε)-factor approximation for k-median and k-means clustering in low-dimensional Euclidean spaces can be computed in 2^{O(1/ε)^{d-1}} ⋅ n ⋅ polylog(n) time, which is nearly optimal under the Gap Exponential Time Hypothesis. Novelty: ClaimNovelty.METHODOLOGICAL. Consensus alignment: ConsensusAlignment.NEUTRAL.

What question did this study set out to answer?

The study aims to enhance the approximation methods for k-median and k-means clustering problems in low-dimensional Euclidean spaces.

May 29, 2026Open Access

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

Key Points

The study aims to enhance the approximation methods for k-median and k-means clustering problems in low-dimensional Euclidean spaces.
Improved the running time of approximation algorithms to 2^{O(1/ε)^{d-1}} ⋅ n ⋅ polylog(n)
Demonstrated a lower bound based on the Gap Exponential Time Hypothesis for 3-SAT.
Analyzed the implications of the new running time on approximation solutions.
Improvement in approximation running time for clustering problems.
Established a matching lower bound indicating limits of algorithm efficiency under certain hypotheses.

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+ε) -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.

Bookmark

View Full Paper