Probabilistic Considerations in the Analysis of Algorithms

算法分析中的概率考虑

• 批准号: 9225008
• 负责人: ALAN FRIEZE
• 金额: $ 15.9万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-07-15 至 1997-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9225008&HistoricalAwards=false
• 关键词: Probabilistic; Considerations; Analysis; Algorithms

Probabilistic considerations arise in the analysis of algorithms in at least two ways. (1) First, in a randomized algorithm the outcomes of random events are used to determine the progress of the algorithm. Randomization is now a standard tool of the computer scientist. (2) A second problem area has instances from some probability distribution and looks to understanding the average performance of a particular algorithm, which is often far better than its worst case. Both aspects are extremely important and this work addresses a number of problems in these two areas. In the area of randomized algorithms, these topics are investigated; (a) random walks on graphs and their application to problems of computing volume; (b) finding edge disjoint paths in expander graphs; (c) counting problems and a randomized dual simplex algorithm; (d) applications of sphere separators in parallel algorithms; and (e) randomized heuristics. In the area of probabilistic analysis, random instances of: (f) the satisfiability problem; (g) graph matching problems; and (h) Hamilton cycle and traveling salesman problems, are considered; as well as (i) the study of explicit constructions for the token distribution problem.

在算法分析中，概率因素至少在两方面出现。(1)首先，在随机化算法中，使用随机事件的结果来确定算法的进度。随机化现在是计算机科学家的标准工具。(2)第二个问题领域有来自某些概率分布的实例，并试图理解特定算法的平均性能，这通常比最坏情况要好得多。这两个方面都非常重要，这项工作解决了这两个领域的一些问题。在随机算法领域，对这些主题进行了研究；(a)图上的随机漫步及其在计算体积问题中的应用；(b)寻找展开图中的边不相交路径；(c)计数问题和随机对偶单纯形算法；(d)球体分离器在并行算法中的应用；(e)随机启发式。在概率分析领域，随机实例：(f)可满足性问题；(g)图匹配问题；(h)考虑了汉密尔顿循环和旅行推销员问题；以及(i)研究令牌分配问题的显式结构。