第13回研究会
第13回研究会を以下の通り開催いたしました．
- 日時：2017年 10月 14日 (土) 13:30〜
- 会場：電気通信大学 東3号館3階マルチメディアホール (301号室)
アクセス：http://www.uec.ac.jp/about/profile/access/ (学内マップ27番の建物)
- 講演者１：高邉 賢史 氏 (名古屋工業大学大学院工学研究科情報工学専攻)
- 題目：組合せ最適化問題に対する近似アルゴリズムの典型性能評価と相転移現象
- 概要：組合せ最適化問題の多くは多項式時間での厳密な求解が困難であり，近似アルゴリズムの開発と性能評価が重要視されている．その近似精度の評価としては，問題のインスタンスの中での最悪性能が従来調べられてきたが，近年ではランダムに生成されるインスタンスに対する典型（平均）近似性能も興味をもたれている．本講演では，主に統計力学的な手法を用いた典型近似性能の解析的な評価法と典型近似性能に関する相転移現象について概説する．本講演の内容の一部は福島孝治氏（東京大学），前原貴憲氏（理化学研究所）との共同研究である．
- 講演者２：河瀬 康志 氏 (東京工業大学工学院経営工学系)
- 題目：予算制約付き安定マッチング問題に対する近似アルゴリズム
- 概要：予算制約付き安定マッチング問題とは，病院に課せられた予算制約のもとで，病院と研修医との間の安定マッチングを求める問題である．予算制約のある状況では，安定マッチングは存在するとは限らないため，その近似解を求めることを考える．本講演では受入保留方式と除去可能オンラインナップサック問題に対するアルゴリズムを組み合わせた解法を提案する．本講演は岩崎敦氏（電気通信大学）との共同研究に基づくものである．
戻る
