第1回研究会（２００６年４月１５日（土） １４時 〜）講演概要
会場： 上智大学 四谷キャンパス ３号館５階 ３−５３３
講演者：
牧野 和久 氏 （東京大学）
タイトル：
マトロイドに関連して現れる列挙問題について
概要：本講演では，マトロイド関連して現れる列挙問題について主に 計算量の観点から述べる． 例えば，マトロイドの独立集合に対するオラクルが与えられたとき， その基は多項式時間遅延で効率よく列挙できることが知られているが， マトロイドのサーキットが多項式時間遅延で解けるかどうか分かっていない． また，最近，極小な連結全域集合の列挙問題が単調な論理関数の双対化問題と （多項式時間）等価であることが分かってきた． 本講演では，これらの話題に対して，最新の成果とともに未解決問題について も議論する．
講演者：
大石 泰章 氏 （東京大学）
タイトル：
ロバスト半正定値計画法のための領域分割型アプローチ
概要： ロバスト半正定値計画問題は係数行列に不確かなパラメータ を含む半正定値計画問題であり，ロバスト制御において重要 であるとともに，多項式計画問題の一般化にもなっている． 本発表では，あるクラスのロバスト半正定値計画問題を解く ための領域分割型アプローチについて紹介する．本アプローチ では，パラメータの領域の分割に基づいて，与えられたロバ スト半正定値計画問題を近似した問題を解く．領域の分割を 細かくすることによって，近似精度を任意に上げることが可 能である．同種のアプローチとして二乗和多項式に基づくも のが有名であるが，これとは違って，近似精度を分割の細か さの関数として陽に評価することができる．また，計算量を 減らすための工夫についても議論する予定である． 本研究は，江本健斗氏，猪阪佑介氏との共同研究である．
ホーム
Copyright, S@CO All rights reserved, 2006.
