Probabilistic Considerations in the Analysis of Algorithms

在分析算法时，至少有两种可能的考虑。 (1)首先，在随机算法中，随机事件的结果用于确定算法的进度。 随机化现在是计算机科学家的标准工具。 (2)第二个问题领域有一些概率分布的实例，并希望了解特定算法的平均性能，这通常远远优于其最坏情况。 这两个方面都极为重要，这项工作解决了这两个领域的一些问题。 在随机算法领域，研究了以下主题：（a）图上的随机游动及其在计算体积问题中的应用;（B）在扩展图中寻找边不相交路径;（c）计数问题和随机对偶单纯形算法;（d）球分离器在并行算法中的应用;以及（e）随机算法。 在概率分析领域，随机实例：（f）可满足性问题;（g）图匹配问题;和（h）汉密尔顿循环和旅行商问题，被认为是;以及（i）令牌分配问题的显式构造的研究。

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.