ネットワーク単体法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/03 06:14 UTC 版)
ネットワーク単体法（ネットワークたんたいほう、別称：ネットワークシンプレックス法[1]、英: network simplex algorithm）とは、数理最適化においてグラフ理論に特化した単体法のことを指す。ネットワーク単体法は主に最小費用流問題を解くために使用される。実践においてネットワーク単体法は同じ規模のネットワーク問題に対する線形計画問題を解く速度は一般の単体法と比べて約200から300倍速く解くことも可能とされる[2]。
歴史
ネットワーク単体法は提案されて以降、実践では非常に効率よく問題を解くことが可能であることは知られていたが、アルゴリズムの計算複雑性については長らく多項式時間のアルゴリズムであるかが未解決問題とされてきた。1995年、ジェームズ・オーリンによってネットワーク単体法の時間計算量が頂点数 
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) |
|||||
|---|---|---|---|---|---|
| グラフ理論 |
|
||||
| ネットワークフロー |
|
- ネットワーク単体法のページへのリンク
