Algorithms and Complexity with Concentration on Probabilistic Analysis

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

The aim of this research is to develop new results in the probabilistic analysis of algorithms. In particular, this project will concentrate on three areas: Random walks on graphs: the aim is to improve the complexity of an algorithm for computing volume and to develop randomized counting schemes for some Randomized heuristics: the goal is to determine whether randomization helps in some heuristics for combinatorial optimization. Average performance of algorithms: algorithms with good avverage case performance will be developed for NP-hard problems and for problems which are complete for P.