線形相補性問題の符号可解性
スポンサーリンク
概要
- 論文の詳細を見る
線形相補性問題(LCP)とは,線形計画や凸二次計画を特殊ケースとして含む数理計画問題である.LCPが符号可解であるとは,解の取りうる符号パターンの集合が係数要素の大きさによらずに定まることを言う.本研究では,係数行列の対角要素が全て非零であるLCPに対して,その符号可解性に対する必要十分条件を与える.そして,符号可解LCPの解の符号パターンを効率的に得るための組合せ的解法を提案する.その計算量はO(γ)(γは係数の非零要素数の和)である.
- 一般社団法人情報処理学会の論文
- 2007-09-21
著者
関連論文
- 2-D-2 コーダル構造を持つ半正定値対称行列に対する極大クリーク行列分解の直接的な証明(離散・組合せ最適化(5))
- 対称二部グラフのマッチング構造
- 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
- 数理計画と組合せ的行列理論(最先端を目指す若手研究者達)
- 数理計画法における符号可解性(研究会推薦博士論文速報)
- 平成21年春季研究発表会ルポ(情報の窓)
- 2-C-3 線形相補性問題の符号可解性(グラフ・ネットワーク)
- 1-B-6 線形計画問題の符号可解性(組合せ最適化(1))
- 符号対称行列のSylvester指数(組合せ最適化(6))
- 線形相補性問題の符号可解性
- 1-D-5 デルタマトロイド制約付きマッチング(離散最適化(1))
- 1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))
- 2-F-2 二部グラフ上の最適予算配分問題に対する高速アルゴリズム(離散最適化(4))
- 2-A-11 ロバスト独立システム(離散最適化(3))