Algorithms and Complexity with Concentration on Probabilistic Analysis

这项研究的目的是在算法的概率分析中发展新的结果。特别是，这个项目将集中在三个方面：图上的随机游动：目的是提高计算体积的算法的复杂性，并开发一些随机计数方案随机化启发式：目标是确定随机化是否有助于组合优化的某些启发式方法。算法的平均性能：对于NP-Hard问题和P完全问题，将开发具有良好平均情况性能的算法。

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.