Designing Efficient Discrete Algorithms with High Quality and High Performance

本研究的目的是从理论和实践的角度对高效、高质量、高性能的离散算法进行研究，为21世纪重要的信息技术之一--算法研究的发展做出贡献。为实现这一目标，我在计算几何、图网络算法、组合优化、并行和分布式算法等领域研究了为设计高效、高质量和高性能的算法而开发的重要技术。特别是在半定规划和网络流技术的基础上，通过与国际上领先的研究人员交流思想，对高性能的离散算法进行了研究。通过这些研究，我可以在VLSI设计、信息网络和实际应用中提出高质量和高性能的高效算法。具体地说，针对最大可满足性问题，提出了一种具有世界最好性能记录的新算法。我还在学生的帮助下实现了算法以及其他研究人员提出的算法，并进行了计算实验，以便从理论和实践的角度对新算法进行评估。这项研究的结果发表在世界领先的期刊和研讨会上。有鉴于此，本研究的目的可以说是令人满意的。

The objective of this research is to do research on efficient discrete algorithms with high quality and high performance from both theoretical and practical points of view and to contribute to the development of algorithmic researches which will be one of the important information technologies in the 21st centuary. To achieve this objective, we have done the following researches.I made an investigation on important techniques developed for designing algorithms which are not only efficient but also 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, I made an investigation on discrete algorithms with high performance by exchanging ideas with leading researchers in the world. Throught this investigation, I could propose efficient 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, I proposed a new algorithm with the world best record in the performance. I also implemented the algorithms with the helps of students as well as algorithms previously proposed by other researchers 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. In view of this, the objective of this research can be said to be satisfatorily achieved.