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）通过采用上述想法，为顶点着色问题开发了近似和精确的算法。确认它们对于许多随机图和DIMAC基准标记图非常有效。（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。

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

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

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

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

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

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

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

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