最小費用流問題のためのネットワーク単体擬乗数アルゴリズムの計算実験
スポンサーリンク
概要
- 論文の詳細を見る
最小費用流問題はネットワーク最適化における最も基本的な問題の一つである. 最小費用流問題を解く, 多くの優れた多項式時間のアルゴリズムがあるが, 実用的にはそのインプリメントの簡単さと速さの両面から, ネットワーク単体法が広く用いられている. その実用性に反して, 最近まで理論的には主ネットワーク単体法のピボット数は多項式でおさえられていなかった. 擬乗数法は最近 Orlin によって開発された, 最小費用流問題に対する初の多項式時間主ネットワーク単体法である. 本稿では, この新しい算法をいくつかの方法でインプリメントし, その振舞いを示す.
- 1996-03-15