Development and Applications of Efficient Algorithms for Combinatorial Optimization Problems

组合优化问题高效算法的开发与应用

• 批准号: 09680331
• 负责人: TOMITA Etsuji
• 金额: $ 2.18万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09680331/
• 关键词: Combinatorial optimization; Maximum clique; Maximum weight clique; Maximal clique; Coloring problem; Approximation algorithm; Dominating Set; RNA secondary structure prediction; 色彩問題; 学習理論; 分枝限定法; 近似彩色; ニューラルネットワーク

(1) We have developed branch and bound algorithm for finding a maximum clique in an undirected graph. They successfully employ greedy coloring algorithms to give the upper bounds for the size of a maximum clique. The algorithms are evaluated experimentally for not only a number of random graphs but also DIMACS bench mark graphs and have been proved very efficient. An approximation algorithm is also developed for the maximum clique problem. In addition, efficient branch and bound algorithms are developed for finding a maximum weight clique in a weighted graph. An algorithm for finding all the maximal cliques are established and proved to be very efficient in experiments.(2) Approximate and exact algorithms are developed for the vertex coloring problem by employing the above mentioned ideas. They are confirmed to be very efficient for a number of random graphs and DIMACS bench mark graphs.(3) As extensions of the above algorithms, efficient algorithm are developed for the Traveling Salesman Problem, and RNA Secondary Structure Problem.

(1) 我们开发了用于在无向图中查找最大团的分支定界算法。他们成功地采用贪婪着色算法来给出最大派系大小的上限。该算法不仅针对许多随机图而且还针对 DIMACS 基准图进行了实验评估，并已被证明非常有效。还针对最大团问题开发了近似算法。此外，还开发了高效的分支定界算法来查找加权图中的最大权重团。建立了一种寻找所有最大团的算法，并在实验中证明是非常有效的。(2)利用上述思想，开发了顶点着色问题的近似算法和精确算法。它们被证实对于许多随机图和DIMACS基准图非常有效。(3)作为上述算法的扩展，针对旅行商问题和RNA二级结构问题开发了高效算法。

项目成果

Yasuhiro TAJIMA,Etsuji TOMITA,and Mitsuo WAKATSUKI: "Polynomial time MAT learning of simple deterministic languages with structural counter examples" Trans.IEICE. J81-D-I-4 (in press). (1999)

Yasuhiro TAJIMA、Etsuji TOMITA 和 Mitsuo WAKATSUKI：“带有结构反例的简单确定性语言的多项式时间 MAT 学习”Trans.IEICE。

梅田徳之: "Dominating Set問題に対する分枝限定アルゴリズムとその実験的評価" 人工知能学会全国大会論文集. 12. 253-255 (1998)

Noriyuki Umeda：“支配集问题的分支定界算法及其实验评估”日本人工智能学会全国会议论文集 12. 253-255 (1998)。

山田 剛: "正の例から極限同定可能な言語クラスの統一的拡張手法" 人工知能学会研究会資料. SIG-FAI9703・7. 43-50 (1998)

Tsuyoshi Yamada：“从正面例子中有限识别的语言类的统一扩展方法”人工智能研究小组的材料SIG-FAI9703·7（1998）。

但馬 康宏: "構造反例付き等価性質問を用いた単純決定性言語の多項式時間MAT学習" 電子情報通信学会技術研究報告. COMP97・59. 111-118 (1997)

Yasuhiro Tajima：“使用结构反例的等价问题进行简单确定性语言的多项式时间 MAT 学习”COMP97・59（1997）。

菊池 淳: "グラフ彩色問題における確率アルゴリズムとハイブリッドアルゴリズム" 電子情報通信学会技術研究報告. COMP97・109. 25-31 (1998)

Jun Kikuchi：“图形着色问题的随机算法和混合算法”IEICE 技术报告 25-31 (1998)。