最小費用流問題のためのネットワーク単体擬乗数アルゴリズムの計算実験

参考文献6件
  • 作田 泉
    東京大学大学院工学系研究科計数工学専攻

書誌事項

タイトル別名
  • Computational Testing of the Network Simplex Premultiplier Algorithm for Minimum Cost Flow Problems

この論文をさがす

説明

最小費用流問題はネットワーク最適化における最も基本的な問題の一つである. 最小費用流問題を解く, 多くの優れた多項式時間のアルゴリズムがあるが, 実用的にはそのインプリメントの簡単さと速さの両面から, ネットワーク単体法が広く用いられている. その実用性に反して, 最近まで理論的には主ネットワーク単体法のピボット数は多項式でおさえられていなかった. 擬乗数法は最近 Orlin によって開発された, 最小費用流問題に対する初の多項式時間主ネットワーク単体法である. 本稿では, この新しい算法をいくつかの方法でインプリメントし, その振舞いを示す.
The minimum cost flow problem is one of the most fundamental problems in network optimization. There are a number of distinguished polynomial-time algorithms for it. Practically, however, the network simplex algorithm is chosen due to its simplicity and speed. Despite its practicality, there was no theoretical polynomial bound for the number of pivots in the primal network simplex algorithm until recently. The premultiplier algorithm is the first polynomial primal network simplex algorithm for the minimum cost flow problem proposed recently by Orlin. In this report, I implement this new algorithm in several ways and show the performance.

収録刊行物

参考文献 (6)*注記

もっと見る

詳細情報 詳細情報について

  • CRID
    1574231876907391232
  • NII論文ID
    110002812219
  • NII書誌ID
    AN1009593X
  • ISSN
    09196072
  • 本文言語コード
    en
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ