文献

J-GLOBAL ID：201802290608465713   整理番号：18A0263726

ネットワークフロー問題のための強多項式収縮-膨張アルゴリズム【Powered by NICT】

A strongly polynomial Contraction-Expansion algorithm for network flow problems

著者 (3件)： Gauthier Jean Bertrand (GERAD & HEC Montreal, 3000, chemin de la Cote-Sainte-Catherine, Montreal (Quebec) Canada, H3T 2A7, Canada) ,  Desrosiers Jacques (GERAD & HEC Montreal, 3000, chemin de la Cote-Sainte-Catherine, Montreal (Quebec) Canada, H3T 2A7, Canada) ,  Luebbecke Marco E. (RWTH Aachen University, Chair of Operations Research, Kackertstrasse 7, D-52072 Aachen, Germany)
資料名： Computers & Operations Research  (Computers & Operations Research)
巻： 84  ページ： 16-32  発行年： 2017年 
JST資料番号： H0216B  ISSN： 0305-0548  CODEN： CMORAP  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,n個のノードとアークを含むネットワーク上の容量制約付き最小費用流問題の解を検討した。必要十分最適性条件を満足させる残留ネットワーク上で行うことができる最小平均サイクルキャンセリングアルゴリズム(MMCC)により証明されるが,それは非常に時間がかかることがある。ははるかに小さいネットワーク上でこれらの条件を利用する収縮したネットワークを導入した。本症ネットワークの構築は非常にフレキシブルなので,著者らは建設選択に依存してその特性を調べた。発症しネットワーク周辺生産される一般的な縮約アルゴリズム。大変興味深いことに,極端な場合としてMMCCと初期ネットワーク単体アルゴリズムの両方をが判明した。展開法を用いた解を導くことにより,MMCCからの理論的結果を回復することができた。そのようなものとして,O(m ~3 n ~2)時間で走行する強多項式膨張アルゴリズムを得た。はない実行時計算量の改善,展開法は,MMCCの挙動,すなわち最適パラメータに相とジャンプの非常に実用的な観察に固着されていない。溶液時間は有意に減少し,インスタンスのサイズが増加するにつれてよりも。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *ネットワーク ,  最小費用流問題 ,  アーク放電 ,  計算量 ,  縮約 ,  *多項式 ,  *アルゴリズム
準シソーラス用語： 最適パラメータ ,  最適性 ,  容量制約 ,  *ネットワークフロー , 【Automatic Indexing@JST】

著者キーワード (6件)： ネットワークフロー問題 ,  残留ネットワーク ,  短縮ネットワーク ,  最小平均コスト周期 ,  複雑性解析 ,  強多項式アルゴリズム

分類 (2件)： 計算機網  (JC03000K) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (6件)： ネットワークフロー ,  問題 ,  多項式 ,  収縮 ,  膨張 ,  アルゴリズム