著者

森山 園子

出版者

東北大学

雑誌

若手研究(B)

巻号頁・発行日

2011

---

線形計画問題(LP)を解くアプローチの1つに,単体法[Dantzig(1947)]に始まるピボットアルゴリズムがある。多項式時間ピボットアルゴリズムの存在の解明はLPにおける重要な未解決問題である。本研究では,多項式時間達成の可能性があるピボット規則として近年注目を集めている最小訪問規則[Zadeh(1980)]に着目し,以下目標を通じてこの未解決問題の解決に挑んだ。(1) ピボットアルゴリズムの振る舞いを記述するLPグラフの列挙法を構築;(2) 最小訪問規則から着想した履歴依存型ピボット規則の振る舞いをLPグラフ上で解析;(3) ピボット規則の適用回数に関する予想の成立・不成立を検証