Skip to content
Preprint

Dimension Reduction and Coresets for Min-Sum $k$-Clustering

Oct 2026 · 0 citations
Computer Science

Abstract

The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two standard sketching methods, dimension reduction and coresets, which represent the input more compactly while preserving the min-sum cost of every $k$-partition up to $1\pm\varepsilon$ factor. Our first contribution addresses dimension reduction in Euclidean space. The Johnson-Lindenstrauss (JL) Lemma readily implies that a random linear map to target dimension $t=O(\varepsilon^{-2}\log n)$ preserves, with high probability, the min-sum cost of all $k$-partitions. We show that target dimension $t=O(\varepsilon^{-2}(ddim\cdot\log(1/\varepsilon)+\log k+\log\log n))$ suffices for Euclidean inputs of doubling dimension at most $ddim$, and moreover this bound is nearly optimal. We also show that target dimension $t=O(\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\log\Delta))$ suffices for Euclidean inputs of aspect ratio at most $\Delta$. Our second contribution is to design the first $\varepsilon$-coreset for metric min-sum $k$-clustering. It is actually a movement-based coreset, has size $(1/\varepsilon)^{O(ddim)} k\log n$ for inputs of doubling dimension at most $ddim$, and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.