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.