Approximation Algorithms Based on Network Flow and Semidefinite Programming

本研究的目的是研究基于网络流和半定规划的组合优化问题的高质量、高性能的近似算法，从理论和实践两个方面促进近似算法的发展。更具体地说，我们考虑了网络问题和几何问题，包括最大可满足性、最大独立集、最小集覆盖、VLSI物理设计等，并基于网络流和半确定规划或新提出的方法获得了性能更好的近似算法。为了实现这一目标，我们做了以下研究。本文对计算几何、图网络算法、组合优化、并行和分布式算法等领域中为设计高质量、高性能的近似算法而发展起来的重要技术进行了研究。特别是在半定规划和网络流技术的基础上，通过与国内外研究人员的交流，对高性能的离散算法进行了研究。通过这项研究，我们可以在超大规模集成电路设计，信息网络和实际应用领域提出高质量和高性能的近似算法。具体来说，对于最大可满足性问题，我们提出了一个在性能上具有世界最佳记录的新算法。我们还在学生的帮助下实现了这些算法以及其他研究者之前提出的算法，并进行了计算实验，以便从理论和实践的角度对新算法进行评估。这项研究的结果发表在世界领先的期刊和研讨会上。

The objective of this research is to do research on approximation algorithms with high quality and high performance for combinatorial optimization problems based on network flow and semidefinite programming and contribute to the development of approximation algorithms from both theoretical and practical points of view. More specifically, we consider network problems and geometric problems including maximum satisfiability, maximum independent set, minimum set cover, VLSI physical design and so on, and obtain approximation algorithms with better performance based on network flow and semidefinite programming or on a newly proposed method. To achieve this objective, we have done the following researches.We made an investigation on important techniques developed for designing approximation algorithms which are of high qaulity and of high performance in the fields of computational geometry, graph-network algorithms, combinatorial optimization, parallel and distributed algorithms and so on. Especially based on the semidefinte programming and network-flow techniques, we made an investigation on discrete algorithms with high performance by exchanging ideas with leading researchers in the world. Through this investigation, we could propose approximation algorithms with high qaulity and high performance in the fields of VLSI design, information networks and real world applications. Specifically, for the maximum satisfiability problem, we proposed a new algorithm with the world best record in the performance. We also implemented the algorithms as well as algorithms previously proposed by other researchers with the helps of students and made computational experiments in order to evaluate the new algorithms not only from the theoretical point of view but also from the practical point of view. The results in this research were published in the world leading journals and symposia.