Probability & Statistics Applied to the Theory of Algorithms

9505167斯蒂尔摘要这个项目的目的是加深对欧几里得组合优化的一些中心问题中存在的随机行为的理解。要研究的问题的例子包括旅行商问题的随机模型、最小生成树问题以及它们的几个相关近似。该项目更具体的目标包括(1)进一步发展旅行商问题和最小生成树问题的分布理论，(2)更广泛地发展TALAGRAND的配置函数理论，(3)更好地理解递增序列泛函的尾部行为，以及(4)发展与非最优启发式相关的泛函的基本极限理论。本研究将使用的方法包括TALAGRAND的等周理论、TALAGRAND的分布不规则性理论、次可加欧氏泛函理论、统计估计的一般效率理论和矢量量化理论。这些工具中的每一个本身都相当重要，期望通过研究概率组合优化的具体问题，对这些工具的优点和缺点获得有用的见解。在过去的五年里，概率论和最优化的接口经历了显著的增长，这一发展对理论计算机科学和算法开发的实践都产生了实质性的影响。这个项目的目的是加深对概率在一些困难和重要的计算问题上所能提供的信息和帮助的理解。特别是，该项目旨在开发概率理论，以帮助描述组合优化理论中几个重要变量的行为，组合优化理论是一门研究定义非常大的有限集的函数的最小化和最大化的学科。该项目更具体的目标包括发展通过大量点的最短路径长度的分布理论，这些点的位置由概率分布确定，以及发展一些最重要的优化理论的近似方法的基本概率。

9505167 Steele Abstract The aim of this project is to build a deeper understanding of the stochastic behaviors present in some of the central problems of Euclidean combinatorial optimization. Examples of problems that are to be investigated include the stochastic models of the traveling salesman problem, the minimum spanning tree problem, and several of their related approximations. The more specific objectives of the project include (1) further development of the distribution theory for the traveling salesman problem and minimal spanning tree problem, (2) more extensive development of Talagrand's theory of configuration functions, (3) refined understanding of the tail behavior of the increasing subsequence functional, and (4) development of the basic limit theory for functionals associated with non-optimal heuristics. The methods that will be used in this investigation include Talagrand's isoperimetric theory, Talagrand's theory of irregularity of distribution, the theory of subadditive Euclidean functionals, the general efficiency theory for statistical estimation, and the theory of vector quantization. Each of these tools is of considerable importance in its own right, and the expectation is that useful insight will be gained into the strengths and weaknesses of these tools through the study of the concrete problems of probabilistic combinatorial optimization. The interface of probability theory and optimization has experienced remarkable growth over the last five years, and this development has had substantial impact on both theoretical computer science and the practice of algorithm development. The aim of this project is to build a deeper understanding of the information and assistance that probability can provide in some difficult and important problems of computation. In particular, the project aims to develop probability theory that helps describe the behavior of several important quantities in the theory of combinatorial optimization, a subj ect that studies the minimization and maximization of functions that are defined very large finite sets. The more specific objectives of the project include development of a distribution theory for the length of the shortest path through a large number of points whose locations are determined by a probability distribution, and the development of the basic probability for some of the most important approximation methods of optimization theory.