「組合せ最適化セミナー」

「組合せ最適化セミナー」は,主に大学院学生を対象として, 組合せ最適化の理論とアルゴリズムを,上記のテーマについて詳細に 講義+演習をする形のセミナーです.

RIMS共同研究としての本開催は6回目になりますが, 今年度は東工大グローバルCOE「計算世界観の深化と展開」 との共催として,東工大大岡山キャンパスで行われます. 今回のテーマでの基本から最先端までの成果について, きちんと理解すべきポイントを押さえて講義し, 大学院学生の実力養成を目指します.研究の幅を広げる目的での 隣接分野の研究をしている学生の参加も大いに歓迎します.
宛先メールアドレス: hirai (at) kurims.kyoto-u.ac.jp


開催期間: 2009年7月27日(月)〜7月29日(水)

開催場所:東京工業大学 大岡山キャンパス
       西8号館E棟10階 情報理工学研究科大会議室

研究代表者:藤重 悟(京大・数理解析研)

幹事:平井 広志(京大・数理解析研)

記念写真: 1 2 3

7月27日(月)  岡本吉央:「固定パラメータ・アルゴリズムの設計法」

NP困難な組合せ最適化問題へのアプローチとして, 固定パラメータ・アルゴリズムやパラメータ化計算量理論という 枠組が近年発展してきている. この枠組では厳密に最適解を求める際に問題となる計算量の 超多項式関数的依存性を軽減することを目的の1つとしている. 本講演では,固定パラメータ・アルゴリズムの設計技法の基礎を概観する. 具体的には,固定パラメータ・アルゴリズムの定義から始め, 基礎技法である有界探索木とカーネル化を紹介する. そして,より高度な技法として,木幅の利用,線型計画法の利用, 整数計画法の利用,color codingなどを時間の許す限り議論する.

7月28日(火)  徳山豪:「乱択手法と最適化」

最適化における乱択法の効果についての話題の解説をする. 簡単な導入の後,高密度部分グラフ問題における乱択アルゴリズムと その解析を具体例として,

「徳山 豪:高密度部分グラフの抽出,電子情報通信学会誌2009-2,82-89」

の内容を詳しく解説する. 時間があれば,計算幾何学のトピックにも触れる予定である.

7月29日(水)  河原林健一:「グラフの平面等への埋め込み問題」

本講演では,以下のグラフ埋め込みに関するトピックについて解説する.

1.グラフの平面への埋め込み
2.TutteのBridge Lemma
3.フレームを使ったグラフ埋め込み
4.交差を許したグラフ埋め込み
5.Irrelevant vertexという概念

特に3,5は,Graph Minor Theory等で応用され, 過去20年で大きな成果を挙げてきている.

時間があれば,最先端の研究手法を発表したい.


講演スケジュール:

7月27(月)

7月28日(火)

7月29日(水)