Mathematical Sciences: Probability and Statistics Applied tothe Theory of Algorithms

本项目旨在对欧几里得组合优化的几个问题进行概率分析，同时主要关注涉及最小代价路径、最小生成树、斯坦纳树和最小代价匹配的具体问题。研究的一个关键路线是关于次加性欧几里得泛函的中心极限定理的可能性，特别是对于随机样本的最小生成树的长度。这一问题与连续渗流理论之间有着密切的联系，这两个领域中的任何一个领域的进展都有望对另一个领域产生有益的影响。该项目的总体意义部分来自于这样一个事实，即算法理论中的概率方法已经导致了许多公认的计算突破，此外，由于观察到计算问题与概率论的核心主题有许多持续的相互作用，比如鞅不等式理论、高斯过程和经验过程。本项目旨在发展概率方法的应用，以解决计算机科学家、运筹学研究人员和其他从事离散系统优化问题的人所关心的问题。该建议主要感兴趣的问题的特点是几何、优化和欧几里得空间中随机点集的自然概率模型之间的密切联系。

This project aims to develop the probabilistic analysis of several problems of Euclidean combinatorial optimization while principally focusing on concrete questions involving minimal cost paths, minimum spanning trees, Steiner trees, and minimal cost matchings. One critical line of investigation concerns the possibility of a central limit theorem for subadditive Euclidean functionals, especially for the length of the minimal spanning tree of a random sample. Connections between this problem and the theory of continuum percolation are strong, and progress in either of these two areas can be expected to have useful impact on the other. The overall significance of the project comes in part from the fact that probabilistic methods in the theory of algorithms have already led to a number of well acknowledged computational breakthroughs, and additionally, from the observation that computational problems have many sustained interactions with topics that are central to probability theory, like the theory of martingale inequalities, Gaussian processes, and empirical processes. This project aims to develop the applications of probabilistic methods to problems that are of concern to computer scientists, operations researchers, and others who engage questions of optimization of discrete systems. The particular feature of the problems of main interest to the proposal is that of a close connection between geometry, optimization, and natural probability models for random sets of points in Euclidean space.