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) 对代币分配问题的显式构造的研究。