最小費用流問題に対するSpeculative Contraction法：実用的なアルゴリズムへ向けて

• Item type: SIG Technical Reports(1)
• 公開日: 1992-01-24
• タイトル: 最小費用流問題に対するSpeculative Contraction法：実用的なアルゴリズムへ向けて
• タイトル / 言語: en
• タイトル: A Speculative Contraction Method for Minimum Cost Flows : Toward a Practical Algorithm
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 筑波大学社会工学系
• 著者所属: 日本IBM東京基礎研究所
• 著者所属: 日本IBM東京基礎研究所
• 著者所属: 日本IBM東京基礎研究所
• 著者所属(英): en
• 著者所属(英): Institute of Socio - Economic Planning, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): IBM Research, Tokyo Research Laboratory, IBM Japan
• 著者所属(英): en
• 著者所属(英): IBM Research, Tokyo Research Laboratory, IBM Japan
• 著者所属(英): en
• 著者所属(英): IBM Research, Tokyo Research Laboratory, IBM Japan
• 著者名: 藤重, 悟; 岩野, 和生; 中野, 淳; 手塚集
• 著者名(英): Satoru, Fujishige; Kazuo, Iwano; Jun, Nakano; Shu, Tezuka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最小費用流問題に対する Orlin の強多項式アルゴリズムの変形である Plotkin?Tardos のアルゴリズムに speculative contraction と呼ばれる手法を用いて，実際にインプリメントした際の高速化を図る。Δ scaling phase において Plotkin?Tardos のアルゴリズムは5nΔ以上のフローが流れる枝を縮約するが，speculative contraction 法ではこれよりかなり小さい閾値で縮約を実行し，その際に生じる primal infeasibility については後処理で解消する．実験結果によれば疎なグラフに対しては3．1倍の高速化が確認され，また speculative contraction 法は primal?dual 法にも計算時間でまさった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a new heuristic method, called a speculative contraction method, for minimum cost flows based on the Plotkin and Tardos algorithm, a variant of Orlin's algorithm. In a Δ scaling phase, the Plotkin and Tardos algorithm contracts arcs of flow value more than 5nΔ. However, the speculative contraction method contracts arcs of flow value much smaller than 5n Δ, and corrects the possible primal infeasibility caused by inappropriate contractions at the end. Our experiments show that the new method significantly reduces the running time of the original algorithm. In particular, for sparse graphs, it shows a speed up of 3.1. Moreover, it runs faster than our implementation of the Primal-Dual method. We hope our experimental results on speculative contractions invoke further research toward theoretically and practically faster scaling algorithms.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1992, 号 9(1991-AL-025), p. 1-8, 発行日 1992-01-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会