On Optimal Coreset Construction for Euclidean (k,z)-Clustering

Constructing small-sized coresets for various clustering problems in different metric spaces has attracted significant attention for the past decade. A central problem in the coreset literature is to understand what is the best possible coreset size for (k,z)-clustering in Euclidean space. While there has been significant progress in the problem, there is still a gap between the state-of-the-art upper and lower bounds. For instance, the best known upper bound for k-means (z=2) is min O(k3/2 varepsilon-2),O(k varepsilon-4) [1,2], while the best known lower bound is Omega(kvarepsilon-2) [1]. In this paper, we make significant progress on both upper and lower bounds. For a large range of parameters (i.e., varepsilon, k), we have a complete understanding of the optimal coreset size. In particular, we obtain the following results: (1) We present a new coreset lower bound Omega(k varepsilon-z-2) for Euclidean (k,z)-clustering when varepsilon ≥ Omega(k-1/(z+2)). In view of the prior upper bound tildeOz(k varepsilon-z-2) [1], the bound is optimal. The new lower bound also implies improved lower bounds for (k,z)-clustering in doubling metrics. (2) For the upper bound, we provide efficient coreset construction algorithms for (k,z)-clustering with improved or optimal coreset sizes in several metric spaces. In particular, we provide an tildeOz(k^frac2z+2z+2 varepsilon-2)-sized coreset, with a unfied analysis, for (k,z)-clustering for all z≥ 1 in Euclidean space. [1] Cohen-Addad, Larsen, Saulpic, Schwiegelshohn. STOC'22. [2] Cohen-Addad, Larsen, Saulpic, Schwiegelshohn, Sheikh-Omar, NeurIPS'22.