Mathematical Sciences: Probability and Statistics Applied tothe Theory of Algorithms

数学科学：概率论和统计学在算法理论中的应用

• 批准号: 8812868
• 负责人: J. Michael Steele
• 金额: $ 6.57万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-07-01 至 1990-11-01
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8812868&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Probability; Statistics; Applied

The project will explore seven explicit conjectures in three broad areas of probabilistic analysis of algorithms, empirical processes and random graphs. Several connections between these apparently different areas will be clarified and used in the solutions of the conjectures. Karp's probabilistic polynomial time algorithm for the traveling salesman problem, leads to considerations of random graphs with special properties. Thus the central limit theorem and the large deviation theory of the traveling salesman problem have connections with quantities of interest in the random graph theory such as minimal spanning trees, and minimal matchings. Some of the new techniques used include the theory of Sobolov inequalities and the Efron-Stein inequality. Theory of random trees is developed by putting specific probability distributions on the trees with n vertices. It will be shown that the use of Harper's method leads to a richer theory of random trees. Harper's method in turn leads to connections with the empirical process of lines. The novelty of the research is its problem-driven approach and the elucidation and exploitation of the interconnections of seemingly divergent fields.

该项目将在三个方面探索七个明确的目标。 算法概率分析的广泛领域，经验 过程和随机图。 这些之间的几个联系 显然不同的领域将得到澄清，并在 的解决方案。 卡普概率多项式 时间算法的旅行商问题，导致 考虑具有特殊性质的随机图。 因此 中心极限定理和大偏差理论 旅行商问题与大量的 对随机图论的兴趣，如最小生成 树和最小匹配 使用的一些新技术 包括Sobolov不等式理论和Efron-Stein不等式 不平等 随机树的理论是通过把 有n个顶点的树的概率分布。 它将表明，使用哈珀的方法导致一个 更丰富的随机树理论 哈珀的方法反过来又导致 与线的经验过程的联系。 的新奇 本研究是以问题为导向的研究方法， 和利用看似不同的 领域的