単体法は多項式アルゴリズムであるか？ ―未解決問題解決への布石―
【研究分野】数理情報学
【研究キーワード】
単体法 / 線形計画問題 / 多項式アルゴリズム / 線形計画法 / 強多項式アルゴリズム
【研究成果の概要】
研究期間全体を通じた主な研究成果は次の通りである。（a)単体法に対する実用的なピボット規則である、最急辺降下規則について研究し、反復回数の理論的上界を初めて得ることができた。（b) 線形計画問題に対するLP-Newton法に二分探索法を組み込んだ新しい方法を提案した。提案手法を解析し、反復回数についての理論的示唆を得ることができた。（c) 線形計画問題に対する新しい解法であるChuvanovのアルゴリズムを線形計画問題よりもより広いクラスの問題である、二次錐計画問題や対称錐計画問題に拡張したできた。（d)ある整数計画問題に対する近似アルゴリズムを開発し、その理論的性質を解明した。
【研究代表者】
【研究協力者】 |
| 水野 眞治 | | (Kakenデータベース) |
|
【研究種目】若手研究(B)
【研究期間】2015-04-01 - 2018-03-31
【配分額】1,820千円 (直接経費: 1,400千円、間接経費: 420千円)