标题： 欧几里得最大化和多样性度量的随机降维 显示英文标题

标题： Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

摘要： 随机降维是一种广泛使用的算法技术，用于加速大规模欧氏优化问题。 本文研究了各种最大化问题的降维方法，包括最大匹配、最大生成树、最大旅行商问题 (TSP)，以及各种数据集多样性度量。 对于这些问题，我们表明降维的效果与底层数据集 $X$ 的 \emph{倍增维度} $\lambda_X$ 密切相关——该维度用于测量点集的固有维数。 具体而言，我们证明了目标维度为 $O(\lambda_X)$ 足以近似地保持任何近似最优解的值，并且我们还表明这对于其中一些问题是必要的。 这与经典的降维结果形成了对比，经典的降维结果的依赖性会随着数据集大小 $|X|$ 的增加而增加。 我们还提供了实证结果，验证了在投影空间中找到的解的质量，以及降维带来的加速效果。 显示英文摘要

摘要： Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale 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 \emph{doubling dimension} $\lambda_X$ of the underlying dataset $X$ -- a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that a target dimension of $O(\lambda_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.