Discovery Sagaサイレントキーワード俯瞰

アルゴリズム / グラフマイナー理論 / 固定パラメータ・アルゴリズム / 線形相補性問題 / 疎性 / グラフ彩色 / イマージョン / パッキング / 固定パラメータアルゴリズム / マトロイド交わり / 多項式時間アルゴリズム / 被覆 / 整数性

本研究課題では，離散・連続最適化問題が持つ組合せ的構造に着目し，その構造を有効に利用した効率的アルゴリズムの設計を行なった．離散最適化問題については，グラフ上の最適化問題から生じる詰め込み・被覆型の整数計画問題に対して，構造的グラフ理論の先進的手法を利用することでErdos-Posa性と呼ばれる組合せ的構造を明らかにし，効率的な固定パラメータ・アルゴリズムを設計した．連続最適化問題に関しては，線形相補性問題という一般的な数理計画問題に対して，整数性などの組合せ的性質の解析，および，疎性など内在する組合せ的性質を利用した効率的なアルゴリズムの設計を行なった．

組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 / アルゴリズム / 国際研究者交流 / アメリカ : イギリス / 車両配送問題 / 多項式時間アルゴリズム / 国際情報交換 / ニュージーランド

巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効率よく解ける状況を考察するとともに、巡回セールスマン問題におけるこれらの条件を車両配送問題に適用した場合に、最適がもつ構造を明らかにした。

組合せ最適化 / アルゴリズム / グラフ理論 / 双向グラフ / クローフリーグラフ / 安定集合問題 / 多項式時間アルゴリズム

「双向グラフに対する最適化問題とその解法の研究」という目的で昨年度に引き続き本年度は研究を進めて来た。
昨年度の研究成果“The generalized stable set problem for claw-free bidirected graphs"について、1998年の6月に開催された国際会議Integer Programming and Combinatorial Optimization(査読付き)にて口頭発表を行った。その際の旅費として本年度の研究費を用いた。また本論文はこの会議のプロシーディングスに掲載された。
本年度の研究成果は“A linear time algorthm for the generalized stable set problem on triangulated bidirected graphs"としてまとめ、Journal of the Operations Research Society of Japanに投稿し、1999年3月17〜19日に京都大学で開催されるJapan-Hungarian Symposium on Discrete Mathematics and Its Applicationsにて口頭発表する。また、この成果については来年度開催される国内外の学術会議、研究会においても口頭発表を行う予定である。この成果は本年度計画していた「一般の双向グラフについて一般化安定集合問題に対する効率的な解放の開発」を含むものである。もう一つの計画「平面上の与えられた点集合の最小重み三角形分割問題へのこの解法の応用」については現在研究中でありまだ成果を得るに至っていない。
また開発した解法については、当研究費によって購入した計算機を用いてその実用面での有効性の検証も行った。