Approximation Algorithms Based on Network Flow and Semidefinite Programming

点击翻译按钮获取中文摘要

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.