確率的なシステム上の最適化問題に対する高速近似アルゴリズム

点击翻译按钮获取中文摘要

本年度は,様々なグラフ最適化問題について確率変数の枝重みが与えられる場合に,最適解重みの分布を近似的に計算するための高速なアルゴリズムを2009年10月に国際会議のSAGA2009(査読つき)において発表した.この発表内容をもって,平成19年における本研究の申請時点での研究計画を達成した.また,前年度の研究成果を2009年4月に国際会議のAAAC2009,2009年5月に国際会議のTAMC2009(査読つき)においてそれぞれ発表した.2009年1月時点でJournal of Discrete Algorithmsに採録決定された論文が2009年12月に出版された.2009年11月24日から2010年2月23日にかけてサイモンフレーザー大学(カナダ)を訪問し,Joseph Peters教授・Binay Bhattacharya教授・Tiko Kameda名誉教授と確率的な最適化問題の解法についての共同研究を行った.SAGA2009において発表したアルゴリズムは,グラフ最適化問題の最適解重みの分布関数について下界を与える関数を高速に計算するものである.このアルゴリズムの計算時間は確定的な最適化問題を解く時間と,解候補の数を計算する時間の和として与えられ,論理的な近似比の保証がある.ここでいう近似比とは,(実際には計算の難しい)最適解の分布関数とアルゴリズムの出力した関数との間の逆関数の比の上界である.また,このアルゴリズムは最小全域木問題・最大マッチング問題・巡回セールスマン問題などの組み合わせ最適化問題について,その枝重みが互いに独立な確率変数として与えられる場合に用いる事ができる.次に,研究計画の範囲を超えて,TAMC2009において発表した結果を拡張する事を試みた.有向非巡回グラフの構造について,あるパラメータκ々を導入し,このκが定数で抑えられる場合にそのグラフ中での最長路長さの分布関数を近似計算する手法を対象とした.今年度はこのたが任意に大きいグラフに対応することを試みたが,そのようなグラフについて任意に小さな計算誤差で分布関数を効率的に計算する事は,今回のアプローチでは難しい.また,サイモンフレーザー大学における共同研究では類似の問題として,一通信路におけるメッセージ伝達時間が確率変数として与えられる計算機ネットワークでのブロードキャスト時間の分布を計算する問題について考察した.以上のように,本年度においては平成19年における本研究申請時点の目的を達成し,さらに今後の研究のための挑戦的な課題に対する解決法の検討を行うことができた.