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

スポンサーリンク

概要

• 論文の詳細を見る

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

• 2013-05-10

著者

• 宮田 洋行

  東京大学大学院情報理工学系研究科

• クラウス ローレンツ

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

• 福田 公明

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

• 宮田 洋行

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

• 福田 公明

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

関連論文

• 小さな有向マトロイドの実現可能性の完全な分類
• Analyzing automorphism groups of oriented matroids by semidefinite programming (Computational Geometry and Discrete Mathematics)
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• P行列線形相補性問題の新たな部分クラスの提案
• A New Subclass of P-matrix Linear Complementarity Problems (コンピュテーション)
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• 陰K行列をもつ線形相補性問題と超立方体上の線形計画問題の計算上同値性
• 4次元超立方体上のPLCP向き付けの列拳
• P行列線形相補性問題の新たな部分クラスの提案(一般)

スポンサーリンク