4次元超立方体上のPLCP向き付けの列拳

スポンサーリンク

概要

• 論文の詳細を見る

• あらまし線形相補性問題(LCP)は線形計画問題、凸二次計画、双行列ゲームなど多くの問題に統一的アプローチを与える重要な問題である。一般にLCPはNP困難であるが、係数行列がP行列の場合(PLCP)はいくつも良い性質を持ち、多項式時間可解である可能性を示唆する結果がある。一方、依然としてPLCPの多項式時間アルゴリズムは見つかっておらず、計算複雑度は不明なままである。多項式時間アルゴリズムの候補として、Bard-typeアルゴリズムがあるが、1978年にStickneyとWatsonはBard-typeアルゴリズムを、超立方体グラフに向きをつけ(PLCP向き付け)、そのシンクを探すアルゴリズムとして定式化し、さらに3次元超立方体上でPLCP向き付けを列挙した。本論文では、有向マトロイドの実現可能性問題を通じて、4次元超立方体上のPLCP向き付けを列挙する。また、計算機実験により得られた種々の知見を紹介する。

• 2012-12-03

著者

• 宮田 洋行

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

• 福田 公明

  スイス連邦工科大学チューリッヒ校

• 宮田 洋行

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

• 福田 公明

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

• ローレンツ クラウス

  チューリッヒ工科大学ペレーションズ・リサーチ科

関連論文

• 小さな有向マトロイドの実現可能性の完全な分類
• 双二次最終多項式による有向マトロイドの実現不可能性判定
• Non-LP orientations, non-line shellings, and non-representable oriented matroids
• Analyzing automorphism groups of oriented matroids by semidefinite programming (Computational Geometry and Discrete Mathematics)
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• P行列線形相補性問題の新たな部分クラスの提案
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• 4次元超立方体上のPLCP向き付けの列拳
• P行列線形相補性問題の新たな部分クラスの提案(一般)

スポンサーリンク