Probabilistic Considerations in the Analysis of Algorithms

这是一个联合资助的项目(计算程序的理论，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)一些几何问题。

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.***