線形計画問題に対する最小比閉路消去法とネットワーク最適化問題への適用
スポンサーリンク
概要
- 論文の詳細を見る
最小費用流問題に対し,様々な種類の負閉路消去法が提案されているが,その性能は消去する閉路の選び方に依存する.1989年にWallacherが提案した方法は最小比閉路消去法と呼ばれ,ある種の比を最小にする閉路を各反復で消去することで,弱多項式回反復での終了を実現している.本研究では,単模線形空間上での線形計画問題に対して,最小比閉路消去法を一般化する.また,最小比閉路消去法が最小費用流問題の主,双対問題の両方に対称的に適用出来ることを導くと共に,強多項式時間で終了するか否かという疑問について否定的な答を与える.
- 一般社団法人情報処理学会の論文
- 1997-03-14
著者
-
塩浦 昭義
東京工業大学
-
塩浦 昭義
東京工業大学 数理・計算科学専攻
-
McCORMICK Thomas
Faculty of Commerce and Business Administration, University of British Columbia
-
Mccormick Thomas
Faculty Of Commerce And Business Administration University Of British Columbia
関連論文
- Efficient Algorithms for Location Problems on Tree Networks
- 一般化ポリマトロイド上のM凸関数(組合せ最適化(3))
- 最小比閉路消去法とネットワーク最適化問題への適用(グラフ・ネットワーク(1))
- 第31回SSORルポ
- Monge性をもつ重みつき2部グラフでの最適κ-割当問題に対する効率的算法(グラフ・ネットワーク(1))
- 木構造ネットワークにおける部分木配置とナップサック問題(ナップサック問題)
- 木構造ネットワークでの道配置問題に対する最適な算法
- 木構造ネットワーク上の部分木配置問題に対する高速解法(グラフ・ネットワーク(1))
- κ-Tree-Coreを線形時間で求めるアルゴリズム(グラフ・ネットワーク(4))
- 線形計画問題に対する最小比閉路消去法とネットワーク最適化問題への適用
- 無向グラフにおける全ての全域木の効率的探索法(グラフ・ネットワーク)