学術情報メディアセンターセミナー 「組合せアルゴリズム」
京都大学学術情報メディアセンターでは、月に一度、各分野でご活躍の講師をお招きし、それぞれの研究開発活動の内容や現在抱えている課題についてご紹介いただき、参加者を含めて広く議論を行う機会として、月例セミナーを開催しております。
1月27日の学術情報メディアセンターセミナーでは、東京工業大学 学術国際情報センター 情報基盤部門の伊東利哉氏をお招きし、ご講演いただきます。学内外を問わず多数の方の参加をお待ちしております。
開催要項
| 日時 | 2009年1月27日（火曜日）16時30分～18時30分 |
|---|---|
| 場所 | 京都大学 学術情報メディアセンター 南館2階 202マルチメディア講義室 （お身体の不自由な方にはエレベーターをご利用いただけますので事務室にお申し付けください。） |
| 参加費用 | 無料 |
| 参加申込み | 不要 |
| 問い合わせ | 京都大学 学術情報メディアセンター 宮崎修一 TEL: 075-753-7418 shuichi＊media.kyoto-u.ac.jp （＊を@に変えてください） |
| 主催 | 京都大学 学術情報メディアセンター |
| 懇親会 | カンフォーラにて開催いたします。（一人2,000円程度） |
プログラム
16時30分～17時30分
| 講演者： | 伊東 利哉 氏 （東京工業大学 学術国際情報センター 情報基盤部門 教授） |
| 講演題目： | 局所復号可能符号の構成 |
| 講演概要： | 局所復号可能符号とはnビットの情報列をNビットの符号語に変換し、符号語の数ビットに問い合わせを行うことで、任意の情報ビットx_を高い確率で復号可能なものを言う。一般に、問い合わせ回数kと符号長Nにはトレードオフの関係が存在する。本講演では、組合せ構造から局所復号可能符号を構成する手法を示し、問い合わせ回数kと符号長Nの関係を提示する。また、局所復号可能符号から通信量の少ないプライバシー保存情報獲得（PIR: Private Information Retrieval）がどのように構成されるかについても紹介する。 |
17時30分～18時30分
| 講演者： | 宮崎 修一 （京都大学 学術情報メディアセンター 准教授） |
| 講演題目： | 安定マッチング問題に対する近似アルゴリズム |
| 講演概要： | 安定マッチング問題とは、2組のグループ（例えば男性グループと女性グループ）の各自が、相手のグループのメンバーを順位づけした希望リストに基づいて、「安定」なマッチングを求める問題である。本問題は、研修医配属や学校配属、腎臓移植のペアリング、チェスの対戦組合せの決定など、様々な応用が知られている。本講演では、安定マッチングの基本的な性質を紹介するとともに、NP困難な最適化バリエーション（男女平等安定マッチング問題、不完全・同順位リストにおける最大安定マッチング問題）に対する近似アルゴリズムの成果を述べる。 |