Approximation Algorithms with High Performance Based on Semidefinite Programming

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

The objective of this research is , surveying recent researches on approximation algorithms with high performance based on the semidefinite programming technique, investigating its usefulness and proposing new approximation algorithms based on the semidefinite programming technique.To achieve, we first made an investigation on similar techniques developped before in most representative network problems, the maximum-weight cut problem, the minimum cost clustering problem, and the maximum satisfiability problem. Through this investigation, I could find that a combined technique of the semidefinte programming with the convex programing is quite useful and obtain new approximation algorithms based on this method. To evaluate the new algorithms not only from the theoretical point of view but also from the practical point of view, I implemented the algorithms with the helps of students as well as the algorithms previously proposed by other researchers and made computational experiments.The results in this research were published in the world leading journals, symposia and Information Processing Society of Japan. In view of this, the purpose of this research can be said to be satisfatorily achieved.