平成13年度第2回KSMAP


日時:9月4日(火) 15:00 〜 17:00

場所:大阪大学 豊中キャンパス 待兼山会館2階 会議室

       会場への案内  

講演題目と講演者

  正則2部グラフの完全マッチングを求める高速アルゴリズム
   高畑貴志  (大阪大学大学院 基礎工学研究科)

  巡回セールスマンゲームとモンジュ性
   岡本吉央 (東京大学大学院総合文化研究科広域システム科学系)


講演要旨:

正則2部グラフの完全マッチングを求める高速アルゴリズム

高畑貴志 (大阪大学大学院 基礎工学研究科)

正則2部グラフの完全マッチングを求める問題は, 枝彩色問題等の応用があり, 
多くのアルゴリズムが提案されてきた. 現時点で最も高速なアルゴリズムは, 
スプレー木を用いた Cole-Ost-Schirra の O( m ) 時間のものであり, 高度な
データ構造を用いない場合は, Scrijver の O( m Δ ) 時間アルゴリズムと 
Rizzi の O( m + n log n log Δ ) 時間のものが挙げられる. (ここで, n は
点数, m は枝数, Δ は次数を表す.) Cole-Ost-Schirra や Schrijver の結果
は, 閉路に沿った枝重みの変更を繰り返す手法を用いている. 一方, Rizzi の
結果は, Cole-Hopcroft によるオイラー閉路を利用してグラフを分割するアル
ゴリズムに, 互除法に対応したグラフ簡略化手法を適用して高速化したもので
ある. 

本発表では, これらのアルゴリズムを解説する. また, 牧野-高畑-藤重に
より提案された O( m + n log n log Δ ) 時間のアルゴリズムも紹介する. 
このアルゴリズムは, グラフを分割せず枝重みの変更のみを繰り返す点に特徴
があり, 高度なデータ構造を用いないで実装できるという利点を持つ.



巡回セールスマンゲームとモンジュ性

岡本吉央 (東京大学大学院総合文化研究科広域システム科学系)

幾つかの大学が有名な先生を招いて各大学で講演してもらうとき,その先生の
総旅費をそれらの大学で負担するわけですが,それをどのように負担するのか
という問題を協力ゲームの枠組で議論します.
これが巡回セールスマンゲームです.
巡回セールスマンゲームと言われる理由は,特性関数が巡回セールスマン問題
を解くことによって得られるからです.
私の話はこの協力ゲームのコアが非空になるときはどのような場合であるのか,
ということに関する話です.
そして,巡回セールスマンゲームのコアが非空になることと巡回セールスマン
問題の効率よく解ける場合に関係があることがわかりました.
タイトルにあるモンジュ性は巡回セールスマン問題が効率よく解ける場合の一
つです.
定理として,
「距離行列がモンジュ行列である巡回セールスマンゲームのコアは非空である」
ことが示されました.
今回は,この定理とそれにまつわる事柄を組合せ最適化もゲーム理論もご存じな
い方でもわかるようにお話ししたいと思います.
21名の参加がありました. 参加して下さった方々に御礼申し上げます.
高畑 貴志(takabatake@sys.es.osaka-u.ac.jp)
<最終更新作成日時 2001年9月17日 >