最大平衡流問題に対するネットワーク単体法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では、最大平衡流問題、つまり各枝の流れがその総流量の一定の比率以下であるという制約の下で総流量が最大になる流れを見出す問題に対して、一つのネットワーク単体法を提案する。また、最大流問題に対するネットワーク単体法の強基底概念を一般化して、本アルゴリズムの有限性を証明する。さらに、この問題で整数値の流れを考えて、平衡係数関数が一定となる場合に最大平衡整数流問題が多項式時間で解けることを示す。
本論文では、最大平衡流問題、つまり各枝の流れがその総流量の一定の比率以下であるという制約の下で総流量が最大になる流れを見出す問題に対して、一つのネットワーク単体法を提案する。また、最大流問題に対するネットワーク単体法の強基底概念を一般化して、本アルゴリズムの有限性を証明する。さらに、この問題で整数値の流れを考えて、平衡係数関数が一定となる場合に最大平衡整数流問題が多項式時間で解けることを示す。