構造解析を基にした組合せ最適化アルゴリズムの効率化に関する研究

今年度は以下の3つ(a)「0-1多面体の構造解析」(b)「重み付きグラフにおける全域木の重み順全列挙アルゴリズムの開発」(c)アルゴリズムの平均的な振る舞いの評価に関する研究」を研究目的とした。(a)に関しては、グラフの最大安定集合問題、グラフの辺(または頂点)の彩色問題に関連した0-1多面体の特殊な面がある半順序集合のイデアル全体から作られる0-1多面体と合同であるという構造を明らかにした。また、この構造を利用し、最大安定集合問題などに対する発見的な方法を提案した。この成果は論文としてまとめ、アメリカ合衆国のミシガン大学で開催された第15回数理計画国際シンポジウム(15th International Symposium on Mathematical Programming)や福岡で開催された第3回アジア太平洋地区オペレーションズ・リサーチ会議(The Thrid Conference of the Association of Asian-Pacific Operational Societies within IFORS)など国内外の会議において口頭発表し、国際的論文誌であるMathematical Programmingに掲載されることになった。(b)に関しては、重み順ではないがグラフの全域木を列挙する時間計算量の意味でも空間計算量の意味でも最適なアルゴリズムを開発した。既存のアルゴリズムで二つの計算量の意味で最適なものはなく、このアルゴリズムが初めてのものである。この研究成果は、論文としてまとめ、第15回数理計画国際シンポジウムや第3回アジア太平洋地区オペレーションズ・リサーチ会議など国内外の会議において口頭発表し、国際的な論文誌であるSIAM Journal on Computingに投稿した。研究目的(c)に関しては、今年度中には論文として発表できるような成果は残念ながら得られなかったが、今後も継続して研究をしていく。本年度は、補助金によって設備としてX端末を購入し、現有設備であるワークステーション(平成4年度科研費により購入)と接続し、論文や発表原稿・OHPの作成、実験結果のグラフィック表示など有効利用した。

今年度は以下の3つ(a)「0-1多面体の構造解析」(b)「重み付きグラフにおける全域木の重み順全列挙アルゴリズムの開発」(c)アルゴリズムの平均的な振る舞いの評価に関する研究」を研究目的とした。(a)に関しては、グラフの最大安定集合問題、グラフの辺(または頂点)の彩色問題に関連した0-1多面体の特殊な面がある半順序集合のイデアル全体から作られる0-1多面体と合同であるという構造を明らかにした。また、この構造を利用し、最大安定集合問題などに対する発見的な方法を提案した。この成果は論文としてまとめ、アメリカ合衆国のミシガン大学で開催された第15回数理計画国際シンポジウム(15th International Symposium on Mathematical Programming)や福岡で開催された第3回アジア太平洋地区オペレーションズ・リサーチ会議(The Thrid Conference of the Association of Asian-Pacific Operational Societies within IFORS)など国内外の会議において口頭発表し、国際的論文誌であるMathematical Programmingに掲載されることになった。(b)に関しては、重み順ではないがグラフの全域木を列挙する時間計算量の意味でも空間計算量の意味でも最適なアルゴリズムを開発した。既存のアルゴリズムで二つの計算量の意味で最適なものはなく、このアルゴリズムが初めてのものである。この研究成果は、論文としてまとめ、第15回数理計画国際シンポジウムや第3回アジア太平洋地区オペレーションズ・リサーチ会議など国内外の会議において口頭発表し、国際的な論文誌であるSIAM Journal on Computingに投稿した。研究目的(c)に関しては、今年度中には論文として発表できるような成果は残念ながら得られなかったが、今後も継続して研究をしていく。本年度は、補助金によって設備としてX端末を購入し、現有設備であるワークステーション(平成4年度科研費により購入)と接続し、論文や発表原稿・OHPの作成、実験結果のグラフィック表示など有効利用した。