pipette
ESEspañol

Dimension Reduction and Coresets for Min-Sum -Clustering

Asaf Dallal, Robert Krauthgamer

Preprint

In the authors' words

The min-sum -clustering problem asks to partition an input of points into 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 -partition up to 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 preserves, with high probability, the min-sum cost of all -partitions. We show that target dimension suffices for Euclidean inputs of doubling dimension at most , and moreover this bound is nearly optimal. We also show that target dimension suffices for Euclidean inputs of aspect ratio at most . Our second contribution is to design the first -coreset for metric min-sum -clustering. It is actually a movement-based coreset, has size for inputs of doubling dimension at most , and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.