Randomizationin Graph Optimization

图模型许多特定的结构，包括交通网络，道路，铁路，飞行路径，计算机网络和超大规模集成电路。 虽然图是非常一般的，但它们具有大量的结构，使得可以比较少约束的优化问题更有效地解决图优化问题。 因此，图优化已经发展成为数学优化的一个大的子领域。随机化在图的优化算法的设计中提供了几个重要的好处。 随机算法通常比确定性算法运行得更快，并给出更好的答案。 此外，由于它们通常比确定性算法更简单，因此随机算法更容易实现和维护，并且在实践中表现得更好。 最大流和最小割问题，这可能是最广泛研究和应用的图优化问题，可以精确地解决__主要目标是设计更快，更简单，更实用的算法，以达到正确的答案。 其他问题，如图的着色和二分法，网络的可靠性分析，以及低成本高连通性网络的构建，都很难精确地解决，主要目标是找到有效的算法，使答案尽可能接近难以捉摸的最优解。 因此，实验分析的算法将进行比较，在实践中的其他算法的性能。

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.