最小費用流問題に対する多項式時間の双対単体法

スポンサーリンク

概要

• 論文の詳細を見る

• 1984年に、伊倉とNemhauserはヒッチコック型の輸送問題に対して双対単体法による多項式時間アルゴリズムを提案している。一般的な最小費用流問題がヒッチコック型の輸送問題に帰着されるという事実により、伊倉-Nemhauserのアルゴリズムは、また同時に、最小費用流問題を解くことができる。本論文では、最小費用流問題を解くにあたって、その問題をヒッチコック型の輸送問題に帰着させるのではなく、次の立場からアルゴリズムを求める。つまり、伊倉-Nemhauserのアイデアを直接、一般のネットワークに拡張し、最小費用流問題を解くための双対単体法による多項式時間アルゴリズムを提案する。

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• 中山 明

  小樽商科大学

• Nakayama A

  Otaru Univ. Jpn

関連論文

• Another Easy Proof of NP-Completeness on the Maximum Integral Vertex-Balanced Flow Problem
• An Algorithm For The Maximum Balanced Flow Problem
• 最小費用流問題に対する多項式時間の双対単体法
• 平衡係数関数が一定となる場合の最大平衡フロー問題に対する多項式時間アルゴリズム

スポンサーリンク