平成１１年度５月　最適化とアルゴリズム研究部会 報告

• 日時：5月22日（土） 14:00 〜 17:30
• 場所：上智大学7号館12階第1215号室
• 参加者：31名

• 発表１：土谷 隆氏 (統計数理研究所）

  『Euclidean Jordan Algebra と主双対内点法』

  Euclidean Jordan Algebra を用いることで, 等質自己双対錐上の線形計画問題と その上での主双対内点法は統一的に取り扱うことができる. 本講演では，Euclidean Jordan Algebra の枠組で扱える問題のクラスについて述べ，多項式内点法の多項式 性の証明がどのよう取り扱えるかについて半正定値計画問題や2次錐計画問題の場合 と対応づけながら紹介した.

• 岩田 覚氏（大阪大学 基礎工学研究科）

  『線型デルタ・マトロイドのパリティ問題』

  マトロイド・パリティ問題は，マトロイドの共通部分問題と 一般グラフのマッチング問題を含む枠組として, 70年代に 提起され, L. Lovasz によって解かれました. 本講演では, マトロイド・パリティ問題のデルタ・マトロイドへの拡張を 考え，歪対称行列で表現された線型デルタ・マトロイドの場合に 多項式時間で解くアルゴリズムを説明し，最適性を特徴付ける 最大最小定理を示した．また，グラフ理論等への応用についても 触れた．