半正定値計画問題に対するクリロフ部分空間法の適用

概要

論文の詳細を見る
Lovasz数を半正定値計画問題として定式化し、それを内点法によって多項式時間内で解くことが可能である。この場合、内点法の各ステップにおいて、係数行列が密となる線形方程式系を解くことになる。この線形方程式系の大きさはLovasz数を計算するグラフの枝の数と等しくなるため、グラフが大規模になるにつれ、線形方程式系も大規模となる。このとき、線形方程式系の解法として直接法を適用することは、計算時間やメモリ使用量の点で困難となる。このため、直接法を利用する代わりに、クリロフ部分空間法を利用することが試みられてきた。本発表では、これらの枠組みのもと、大規模なグラフに対するLovasz数の計算を行う。このとき、より大きなグラフに対するLovasz数を計算するため、この問題における特有の性質を生かしたいくつかの計算手法を提案する。最後に、実際に大規模なグラフに対するLovasz数の計算を行うことにより、これらの手法の有用性について検証する。
一般社団法人情報処理学会の論文
2001-07-25