日本オペレーションズ・リサーチ学会

「離散アルゴリズムの応用と理論」研究部会

Seminar on Discrete Algorithms: Applications and Theory

2016年3月より, 日本オペレーションズ・リサーチ学会「離散アルゴリズムの応用と理論」研究部会(Seminar on Discrete Algorithms: Applications and Theory)が発足しました. 研究部会の紹介はこちらをご覧下さい.

第14回研究会のお知らせ

第14回研究会(2018年度第4回)研究会を下記の通りに開催いたします.多数の方々のご参加をお待ちしております.

  • 日時: 2018年12月27日(木) 13:00 〜 17:30
  • 会場: 理化学研究所 革新知能統合研究センター
    • 日本橋一丁目三井ビルディング 15階
    • 会場への行き方はこちら
    • 当日は15階のインターフォンにて離散アルゴリズム研究部会参加の旨お伝えください

また,講演会後,講演者とともに離散アルゴリズムについて意見交換を行う会食を予定しております.参加をご希望の方はご登録をお願いいたします.

講演者1:前原 貴憲 氏(理化学研究所)

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


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

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

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

講演者2:今堀 慎治 氏(中央大学)

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


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

過去の研究会の情報はこちら

主査:牧野 和久 (京都大学)

幹事:井出 陽子(三菱重工業(株)),澄田 範奈 (首都大学東京)