平成18年度 第2回 全体会議

開催案内

日時 11月18日(土) 10:00 〜 15:30
会場 名古屋大学 IB電子情報館 IB015
〒464-8603 名古屋市千種区不老町
地図: http://www.nagoya-u.ac.jp/sogo/higasiyama.html

プログラム

10:00-12:00 講演: 安定結婚問題に対する1.875-近似アルゴリズム
宮崎修一 (京大)
講演: 組合せ最適化の地平
岩田覚 (京大)
12:00-13:30 昼休み
13:30-14:00 新世代の計算限界 −その解明と打破−
プロジェクトの基本アイデアと現在までの成果: 岩間一雄 (京大)
14:00-14:30 計算理論の現状と未来: 徳山豪 (東北大)
14:30-15:30 全体討論

講演要旨

安定結婚問題に対する1.875-近似アルゴリズム
講演者:宮崎修一 (京大)
要旨: 同順位と不完全リストを許す安定結婚問題において、 最大サイズの安定マッチングを求める問題はNP困難であり、 P \neq NP ならば 21/19-近似アルゴリズムが存在しないことが知られている。 近似可能性に関しては、2-近似アルゴリズムの存在は容易に示すことができるが、 2よりも真に良い近似度を持つアルゴリズムの存在は未解決であった。 本発表では、本問題に対する1.875-近似アルゴリズムを与える。 (岩間一雄教授および山内直哉氏との共同研究である。)