Probabilistic Considerations in the Analysis of Algorithms

算法分析中的概率考虑

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

CCR-9814411FriezeProbabilistic considerations arise in the analysis of algorithms in at least two important ways. First of all, 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. A second area of consideration is when the problem instances come from some probability distribution and one wants to understand the average performance of a particular algorithm, which is often far better than its worst case.This project attacks a number of problems in these two areas. Topic considered in the area of randomized algorithms included decomposition of matrices, random walks, rapidly mixing Markov chains and min-wise independence. Topics considered in probabilistic analysis include approximation algorithms, packet routing and computational biology.

CCR-9814411Frieze 在算法分析中至少以两种重要方式出现概率考虑因素。 首先，在随机算法中，随机事件的结果用于确定算法的进度。 随机化现在是计算机科学家的标准工具。 第二个需要考虑的领域是，当问题实例来自某种概率分布时，人们想要了解特定算法的平均性能，该算法通常比最坏情况要好得多。该项目解决了这两个领域的许多问题。 随机算法领域考虑的主题包括矩阵分解、随机游走、快速混合马尔可夫链和最小独立性。 概率分析考虑的主题包括近似算法、数据包路由和计算生物学。