第 7 回研究会

  • 日時: 2019 年 5 月 18 日 (土) 13:30--18:00 (開場は 13:00 頃)
  • 会場: 中央大学 後楽園キャンパス 3 号館 3 階 3300 号室 (交通アクセス, キャンパスマップ)
  • 講演 1
    • 講演者: 呉偉氏 (成蹊大学 理工学部 情報工学科)
    • 講演題目: ロバスト組合せ最適化問題に対する行生成アルゴリズム
    • 講演概要: ロバスト最適化とは, 問題の入力に不確定さあるいは曖昧さが内在している場合にも, 信頼できる結果を返すようなモデリング技法及びその解法を指す. 本発表では, 組合せ問題における様々なロバスト最適化モデルを紹介する. 最大後悔最小化基準の問題に対して, Benders-like 分解法と反復双対置換法の 2 種類の行生成アルゴリズムを説明する. また, 反復双対置換法において, ロバスト最適化特有な性質を利用する新たな行生成方法を紹介する. 行生成アルゴリズムの汎用性を確かめるために, ナップサック問題, 多次元ナップサック問題, 一般化割当問題, 集合被覆問題を用いて計算実験を行う. その結果も発表で報告する.
  • 講演 2
    • 講演者: 南和宏氏 (統計数理研究所 モデリング研究系)
    • 講演題目: 表データの最適セル秘匿処理に対するアルゴリズム・マッチング攻撃とその実証的評価
    • 講演概要: 表データのセル秘匿問題は行計, 列計の線形式を内包する表データに対し, 与えられた 1 次秘匿セルの集合の値の保護を拘束条件として, 情報損失を最小化する 2 次秘匿セルの集合を決定する問題である. この問題は一般に NP 困難であるため, 多くの場合に効率的に最適解を算出する Benders 分割の手法を用いたアルゴリズムが提案されている. しかし, この手法では安全性の拘束条件の中で秘匿すべきセル値を参照しているため, セキュリティ・パラメータの知識をもつ攻撃者に対する脆弱性を有する. 本講演ではこの Benders 分割のアルゴリズムを攻撃ツールとして用い, 最適に秘匿された表データの機密セル値が復元できることを実証的に示す.
  • 参加者数: 21 名