線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて

スポンサーリンク

概要

• 論文の詳細を見る

• 今日、線形計画問題が強多項式時間で解けるかは一大未解決問題であり、特に単体法が適当なピボット規則のもと、強多項式時間アルゴリズムになりうるのかが大きく注目されている。単体法の解析において、単体法の可能な振る舞いを記述した線形計画グラフの組合せ的性質を解明することは、その意味で非常に重要である。本論文では、まず線形計画向き付けが完全に組合せ的に特徴づけられる多面体クラスについて知られている結果を振り返った後、頂点数d+2のd次元多面体の線形計画向き付けを考察する。そのような多面体の線形計画向き付けは、Mihalisinにより組合せ的な特徴づけが得られていたが、本論文では、別の特徴づけとして、2009年にAvisとMoriyamaにより提案されたシェリング性でも特徴づけられることを示す。

• 2012-10-24

著者

• 宮田 洋行

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

• 森山 園子

  東京大学ナノ量子情報エレクトロニクス研究機構

• 森山 園子

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

• 宮田 洋行

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

• 青島 良一

  東京大学大学院情報理工学系研究科コンピュータ科学専攻

関連論文

• 小さな有向マトロイドの実現可能性の完全な分類
• BDDを用いたグラフのTutte多項式計算の再考察
• 双二次最終多項式による有向マトロイドの実現不可能性判定
• 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)
• Computational Analysis of Orientations of Matroids (Computational Geometry and Discrete Mathematics)
• 最小包含球問題から得られる4-cubeグラフの向きづけ
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• 三値マトロイドの生成とWhiteの予想に関する実験
• P行列線形相補性問題の新たな部分クラスの提案
• 線形計画向き付けをシェリング性で特徴づけられる多面体クラスについて
• 4次元超立方体上のPLCP向き付けの列拳
• P行列線形相補性問題の新たな部分クラスの提案(一般)
• 三値マトロイドの生成と White の予想に関する実験

もっと見る 閉じる

スポンサーリンク