Approximation Algorithms with High Performance Based on Semidefinite Programming

基于半定规划的高性能逼近算法

• 批准号: 07680370
• 负责人: ASANO Takao
• 金额: $ 1.54万
• 依托单位: CHUO UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 1997
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07680370/
• 关键词: Semidefinite programming; approximation algorithms; performance ratio; maximum satisfiability; 離散アルゴリズム; 充足化可能性; 計算量

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.

本文的研究目的是，综述近年来基于半定规划技术的高性能近似算法的研究成果，研究其实用性，并提出新的基于半定规划技术的近似算法，为此，我们首先研究了在最大权割问题、最小代价聚类问题、最小权割问题、最小权割问题、最大权割问题、最小权割问题、最小权割最大可满足性问题通过这些研究，我发现半定规划与凸规划相结合的方法是很有用的，并在此基础上得到了新的逼近算法。为了从理论和实践的角度对新算法进行评价，我在学生的帮助下实现了这些算法，并对其他研究人员提出的算法进行了计算实验，研究结果发表在世界领先的期刊、研讨会和日本信息处理学会上。鉴于此，本研究的目的可以说是令人满意地实现。

项目成果

T.Ono, T.Hirata and T.Asano: "An approximation algorithm for MAX 3-SAT." Proc.6th International Symposium on Algorithms and Computation (Lecture Notes in Computer Science 1004, Springer) , Cairns. 163-160 (1995)

T.Ono、T.Hirata 和 T.Asano：“MAX 3-SAT 的近似算法。”

T.Asano: "An O (nlog logn) time algorithm for constructing a graph of maximum connectivity with prescribed degrees." Journal of Computer and System Sciences. Vol.51. 503-511 (1995)

T.Asano：“一种 O (nlog logn) 时间算法，用于构建具有规定程度的最大连通性图。”

Takao Asano: "A Theoretical Framework of Hybrid Approaches to MAX SAT" Proc.8th Symposium on Algorithms and Computation. 8. 153-162 (1997)

Takao Asano：“MAX SAT 混合方法的理论框架”Proc.8th 算法与计算研讨会。

Takao Asano: "A Refinement of Yannakakis's Algorithm for MAX SAT" 情報処理学会(アルゴリズム研究会報告). 96-AL-54-11. 81-88 (1996)

Takao Asano：“Yannakakis 的 MAX SAT 算法的改进”日本信息处理协会（算法研究小组报告）96-AL-54-11 (1996)。

T.Asano, T.Ono and T.Hirata: "Approximation algorithms for the maximum satisfiability problem." Nordic Journal of Computing. Vol.3. 388-404 (1996)

T.Asano、T.Ono 和 T.Hirata：“最大可满足性问题的近似算法。”