P行列線形相補性問題の新たな部分クラスの提案(一般)

スポンサーリンク

概要

• 論文の詳細を見る

• P行列線形相補性問題(PLCP)の計算複雑度は現在未解明である。それに対する一つのアプローチとして、P行列の部分クラスを調べることでPLCPへの洞察を得ようとする研究がなされている。本稿では、有向マトロイドを用いて新しいP行列の部分クラスcyclic-P行列を提案する。このクラスは主ピボット変換や主マイナーをとるなどの操作で閉じているいう意味で自然である。また、このクラスの行列はうまく特徴づけられ、数学的にもきれいな構造を持ち、効率のよいアルゴリズムの設計が可能である可能性があり、今後調べる対象として非常に有望である。

• 2013-05-10

著者

• クラウス ローレンツ

  国立情報学研究所|JST, ERATO, 河原林巨大グラフプロジェクト

• 宮田 洋行

  東北大学大学院情報科学研究科

• 福田 公明

  チューリッヒ工科大学理論計算機科学科・数学科

関連論文

• P行列線形相補性問題の新たな部分クラスの提案
• A New Subclass of P-matrix Linear Complementarity Problems (コンピュテーション)
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• 陰K行列をもつ線形相補性問題と超立方体上の線形計画問題の計算上同値性
• 4次元超立方体上のPLCP向き付けの列拳
• P行列線形相補性問題の新たな部分クラスの提案(一般)

スポンサーリンク