第１４回研究会

  • 日時： 2018年12月27日（木） 13:00 〜 17:30
  • 会場： 理化学研究所 革新知能統合研究センター

講演者１：前原 貴憲 氏（理化学研究所）

題目：論理式制約付き単調劣モジュラ関数最大化


単調劣モジュラ関数を適当な制約下で最大化する問題は基本的な組合せ最適化問題であり，機械学習・データマイニングなど幅広い領域に応用をもつ．どのような制約であればどのような近似率が達成可能か，という観点で様々な研究が行われており，マトロイド制約・ナップサック制約を始めとする様々な制約に対する近似アルゴリズムが得られてきた．

本研究では，実行可能領域が「適当なグラフの部分グラフであって，述語論理式で指定されるもの」として与えられる場合を考える．この問題は一般には実行可能解が存在するかの判定すら困難であるが，グラフクラス・論理式クラスを適切に制限することで適当な近似率の解を得ることができる．この結果はCourcelle の「グラフ上の二階述語論理式で記述される条件は木幅定数グラフに対して線型時間で判定可能」や Seeseの「グラフ上の一階述語論理式で記述される条件は次数定数グラフに対して線型時間で判定可能」の劣モジュラ関数最大化版である．

本研究はTomas Rigaux氏 (Ecole Normale Superieure)，石畠正和氏 (NTT研究所) との共同研究である．

講演者２：今堀 慎治 氏（中央大学）

題目：ネットワークにおける経路設計


ネットワークにおける経路設計（経路制御）問題を扱う．対象とするネットワークはインターネットであり，インターネットにおける経路設計には様々な特徴がある．本発表では，はじめにインターネットにおける経路設計に関する代表的な問題設定と経路設計手法を紹介した上で，発表者らがこれまでに取り組んできた2つの問題設定に対する研究内容を紹介する．1つは，マルチパスルーティングと呼ばれる問題設定における結果であり，もう1つはDDoS攻撃への対策を考慮した経路設計手法に関する最近の結果である．