平成19年度 第２回 全体会議

開催案内

日時 12月15日(土)
会場 東北大学 (青葉山キャンパス)
電子情報システム・応物系 南講義棟1階103号室
〒980-8579 宮城県仙台市青葉区荒巻字青葉05
地図 >> アクセス
>> 工学部
>> 全体会議 会場

プログラム

11:30-13:00 幹事会
13:00-13:40 Robust Cost Colorings
　　福永 拓郎 (京都大学)
13:40-14:20 スペクトラル手法と確率伝播
　　山本 真基 (京都大学)
14:20-14:40 休憩
14:40-15:20 あいまい性を考慮した列挙手法
　　宇野 毅明 (国立情報学研究所)
15:20-15:30 休憩
15:30-17:30 全体会議

講演要旨

Robust Cost Colorings
講演者： 福永拓郎 (京都大学 情報学研究科)
要旨： Gを節点重み付き無向グラフ，fを単調非増加関数であるとし， Gにおける節点集合のコストを，その重みの和を入力としたfが返す値と定義す る．本講演では，各色のコストの和を最小化する節点彩色問題の近似可能性につ いて議論する．具体的には，ある条件下において, 一つの彩色が，上のように定 義される任意のコスト関数における定数近似解であることを示す．
スペクトラル手法と確率伝播
講演者： 山本真基 (京都大学 情報学研究科)
要旨： スペクトラル手法は，頂点彩色問題，最大クリーク問題， Ｍｉｎ−Ｂｉｓｅｃｔｉｏｎ問題，ＭＡＸ２ＳＡＴ問題などに対して， 平均的に効率よく解くアルゴリズムに使われてきた手法である． 確率伝播（Belief Propagation）は， 統計力学や符号理論における復号化アルゴリズムなどに使われてきた手法である． 本講演では，確率伝播を用いたアルゴリズムが， 平均的に効率よく解くアルゴリズムに使うことができることを， Ｍｉｎ−Ｂｉｓｅｃｔｉｏｎ問題を例に挙げて示し， 確率伝播の収束性が， スペクトラル手法の平均時解析と同様の証明で説明がつくことを示す．
共同研究者： 渡辺治 (東京工業大学)
あいまい性を考慮した列挙手法
講演者： 宇野毅明 (国立情報学研究所 情報学プリンシプル研究系)
要旨： 近年，列挙手法は多くの情報的な問題解決に用いられているが， 現実のデータを精度よく解析するためには，あいまい性を考慮した 列挙モデルが必要となってきている． 本発表では，グラフからクリークっぽいものを全て見つける列挙問題と， 頻出集合っぽい集合を見つける問題について， 問題の難しさを明らかにし，効率的な解法を提案する．