Probability & Statistics Applied to the Theory of Algorithms

可能性

• 批准号: 9505167
• 负责人: J. Michael Steele
• 金额: --
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1998-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9505167&HistoricalAwards=false
• 关键词: Probability; & Statistics; Applied; Theory

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.

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