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.