Designing Efficient Discrete Algorithms with High Quality and High Performance

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

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.