Randomizationin Graph Optimization

图形模拟许多特定的结构，包括交通网络、道路、轨道和飞行路线、计算机网络和VLSI电路。尽管图是非常通用的，但它们具有大量的结构，使得解决图优化问题比求解约束较少的优化问题更有效。因此，图优化已经发展成为数学优化的一个很大的子领域。随机化在图的优化算法的设计中有几个重要的好处。随机化算法通常比确定性算法运行得更快，并给出更好的答案。此外，由于随机化算法通常比确定性算法更简单，因此随机化算法更容易实现和维护，并且在实践中表现得更好。最大流和最小割问题可能是最广泛研究和应用最广泛的图优化问题，它可以精确地解决--主要目标是设计出更快、更简单、更实用的算法来得到正确的解。其他问题，如图着色和对分，网络可靠性分析，以及低成本、高连通性网络的构建，都是极其困难的--主要目标是找到有效的算法，给出尽可能接近难以捉摸的最优解的答案。所开发的算法只有在理论上感兴趣，除非它们被实际实施。因此，将对这些算法进行实验分析，并将它们在实践中的性能与其他算法进行比较。

Graphs model many specific structures, including transportation networks, roads, rails, and flight-paths, computer networks, and VLSI circuits. Although graphs are very general, they have a great deal of structure that makes it possible to solve graph optimization problems more efficiently than less-constrained optimization problems. Thus, graph optimization has developed as a large subfield of mathematical optimization.Randomization gives several important benefits in the design of optimization algorithms for graphs. Randomized algorithms often run faster and give better answers than their deterministic counterparts. Furthermore, since they are often simpler than deterministic algorithms, randomized algorithms can be easier to implement and maintain and can perform better in practice.This project investigates the uses of randomization in several central optimization problems on graphs. The maximum flow and minimum cut problems, which are perhaps the most widely studied and applicable graph optimization problems, can be solved exactly__the major objective is designing faster, simpler, and more practical algorithms for arriving at the right answer. Other problems, such as graph coloring and bisection, analysis of network reliability, and construction of low-cost high-connectivity networks, are extremely hard to solve exactly__the major objective is to find efficient algorithms that give answers as close as possible to the elusive optimum.The algorithms developed will be of only theoretical interest unless they are actually implemented. Therefore, experimental analysis of the algorithms will be undertaken, comparing their performance in practice to that of other algorithms.