Probabilistic Considerations in the Analysis of Algorithms

点击翻译按钮获取中文摘要

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.