Probabilistic Considerations in the Analysis of Algorithms

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

CCR-9814411FriezeProbabilistic considerations arise in the analysis of algorithms in at least two important ways. First of all, 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. 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.This project attacks a number of problems in these two areas. Topic considered in the area of randomized algorithms included decomposition of matrices, random walks, rapidly mixing Markov chains and min-wise independence. Topics considered in probabilistic analysis include approximation algorithms, packet routing and computational biology.