Probabilistic Considerations in the Analysis of Algorithms

算法分析中的概率考虑

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

This is jointly funded project (between the Theory of Computing Program, CCR and Probability Program, DMS), that started under CCR-92-25008, ``Probabilisitic Considerations in the Analysis of Algorithms''. Probalilistic considerations arise in the analysis of algorithms in at least two important ways: (1) 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 computational scientist; (2) 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. Under this previous grant, CCR-92-08597, probabilistic and algorithmic issues were explored in such areas as: (a) sampling, (b) path problems, (c) counting, (d) heuristics for bisection/k-cut of weighted graphs,(d) greedy algorithms, (e) computational biology, (f) complexity of determining polyhedra from its faces, (g) hypergraphs, and(h) probabilistic combinatorics. This project explores problems in both areas. In (1) the area of randomized algorithms, the problems examined include: (1a) random walks on graphs; (1b) approximation algorithms; and (1c) learning and routing problems. In (2) the area of probabilistic analysis, the problems studied include: (2a) greedy algorithms; (2b) in computational biology, sequencing by hybridization and physical mapping reconstruction for DNA; and (2c) some geometric problems.***

这是联合资助的项目（计算理论计划、CCR 和概率计划、DMS），在 CCR-92-25008“算法分析中的概率考虑因素”下启动。在算法分析中，概率考虑因素至少以两种重要方式出现：（1）在随机算法中，随机事件的结果用于确定算法的进度。 随机化现已成为计算科学家的标准工具； (2) 第二个需要考虑的领域是，当问题实例来自某种概率分布时，人们想要了解特定算法的平均性能，该算法通常比最坏情况要好得多。 根据之前的拨款 CCR-92-08597，在以下领域探讨了概率和算法问题：(a) 采样、(b) 路径问题、(c) 计数、(d) 加权二分/k 割的启发式算法图，(d) 贪婪算法，(e) 计算生物学，(f) 从面确定多面体的复杂性，(g) 超图，以及 (h) 概率组合。 该项目探讨了这两个领域的问题。 在（1）随机算法领域，研究的问题包括：（1a）图上的随机游动； (1b) 近似算法； (1c) 学习和路由问题。 在(2)概率分析领域，研究的问题包括：(2a)贪婪算法； (2b) 在计算生物学中，通过杂交测序和 DNA 物理图谱重建； (2c) 一些几何问题。***