Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

Randomized dimensionality reduction is a widelyused algorithmic technique for speeding up largescale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, max TSP, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the doubling dimension λ X of the underlying dataset X-a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that a target dimension of O(λ X ) suffices to approximately preserve the value of any near-optimal solution, which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence increases with the dataset size |X|. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.