Mathematical Sciences: Probability and Statistics Applied tothe Theory of Algorithms

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

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.