最小平均コストの閉路に基づく劣モジュラ・フロー問題に対する一つのプライマルな算法
スポンサーリンク
概要
- 論文の詳細を見る
最近、GoldbergとTarjanは、最小平均コストの閉路を利用して、最小費用フロー問題に対する多項式時間の算法を提案した。本論文では、GoldbergとTarjanのアプローチを劣モジュラ・フロー問題に適用して、理論的にも興味ある定理を証明する。この定理に基づき、藤重の独立フロー問題の解法とZimmermannの劣モジュラ・フロー問題の解法が、枚数最小の負の長さの閉路の代わりにある種の平均コストが最小な閉路を選ぶことによって有限回で停止することを示す。
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
関連論文
- 劣モジュラ・システムに関連する基多面体のすべての面の特徴づけ
- 分配束上の劣モジュラ関数について
- The Minimum-Weight Ideal Problem for Signed Posets
- 線形計画問題に対する双対内点主シンプレックス法
- Signed Posets for Extreme Points of a Bisubmodular Polyhedron
- ∩,∪-closed Families and Signed Posets
- Proper Bisubmodular Systems and Bidirected Flows
- A Greedy Algorithm for Minimizing a Separable Convex Function over a Finite Jump system
- A Greedy Algorithm for Minimizing a Separable Convex Function over an Integral Bisubmodular Polyhedron
- 最大平衡流問題に対するネットワーク単体法
- 組合せ的制約をもつ線形システムの可制御性,可観測性
- SUMTから乗数法へ(新技術アラカルト)
- New Algorithms for the Intersection Problem of Submodular Systems
- 最小平均コストの閉路に基づく劣モジュラ・フロー問題に対する一つのプライマルな算法