Algorithms and Complexity with Concentration on Probabilistic Analysis

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

The aim of this project is to analyse and develop algorithms (for NP- hard problems) that have a high probability of success. Here, Success means solving the problem exactly or, in the case of optimization problems, to within a small margin of error. A second aim is to improve the complexity, and to extend the application, of a recently developed randomized algorithm for approximating the volume of convex bodies. Generally, graph theoretic problems, packing problems and integer programming will be studied in the context of parallel, as well as serial, algorithms. Pseudo-random inputs and randomized algorithms that use pseudo-random numbers will also be considered.