第11回研究会
第11回研究会を以下の通り開催いたしました．
- 日時：2017年 3月 14日 (火) 13:30〜
- 会場：沖縄県市町村自治会館 4階 第3会議室
- 講演者１：垣村 尚徳 氏 (東京大学大学院総合文化研究科 附属国際環境学教育機構)
- 題目：劣モジュラ関数最大化に対するストリーミングアルゴリズム
- 概要：ストリーミングアルゴリズムとは一連のデータの流れを効率的に処理するためのアルゴリズムであり，クラスタリングやテキスト要約など，入力データがメモリに全て収まりきらないような大規模な最適化問題を省メモリで計算することができる．
本講演では，劣モジュラ関数最大化に対して効率的なストリーミングアルゴリズムを発表する．
具体的には，サイズ制約付き劣モジュラ関数最大化に対する既存の定数近似ストリーミングアルゴリズムを紹介し，そのナップサック制約への拡張を提案する．
本研究はChien-Chung Huang氏(CNRS)，吉田悠一氏(NII)との共同研究である．
- 講演者２：山口 勇太郎 氏 (大阪大学 大学院情報科学研究科 情報数理学専攻)
- 題目：マッチングとパス詰め込み
- 概要：グラフにおけるマッチングおよびパス詰め込みは，組合せ最適化の分野において中心的な話題として20世紀中旬から盛んに研究されてきた．
これらの問題に対する研究を通じて，最大最小定理による良い特徴付けや，増加道に基づく効率的なアルゴリズムなど，様々な概念・技法が発達してきた．
本講演では，一連の研究について紹介しながら基本的な概念をおさらいした後，さらなる拡張に関する講演者らの成果について紹介する．
なお，講演内容の一部は谷川 眞一氏との共同研究に基づくものである．
戻る
