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 的近似算法。”

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: "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) 时间算法，用于构建具有规定程度的最大连通性图。”

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：“最大可满足性问题的近似算法。”