膨胀图在随机算法设计中的应用

Expander Graphs' Application to Randomized Algorithm Designing

介绍了膨胀图的基本理论,组合膨胀与代数膨胀之间的联系,以及膨胀器构造方法等。系统地阐述了膨胀图在随机算法设计中的应用原理和方法。通过对"坏事件"发生的概率上、下界估计,给出了膨胀图在近似算法设计中的应用方法。

The basic theory of expander graph is introduced in this paper, including the relation between combinatorial expanders and algebraic expanders, the construction technique of expander family and so on. The principles and methods of application in randomized algorithm designing are presented systematically. And the application methods of expanders in approximate algorithm are also presented based on the estimate of the upper bound and lower bound of ＂bad incidents＂.