WEKO3
アイテム
最小費用流問題アルゴリズムに対する実験的性能評価
https://ipsj.ixsq.nii.ac.jp/records/31763
https://ipsj.ixsq.nii.ac.jp/records/3176396271caa-4da2-45ab-b22b-a36ae04af1fe
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2006 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2006-01-20 | |||||||
タイトル | ||||||||
タイトル | 最小費用流問題アルゴリズムに対する実験的性能評価 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Experimental Evaluation of Minimum Cost Flow Algorithms | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
広島大学大学院 工学研究科 情報工学専攻 | ||||||||
著者所属 | ||||||||
広島大学大学院 工学研究科 情報工学専攻 | ||||||||
著者所属 | ||||||||
広島大学大学院 工学研究科 情報工学専攻 | ||||||||
著者所属 | ||||||||
広島大学大学院 工学研究科 情報工学専攻 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering Hiroshima University | ||||||||
著者名 |
慶祐, 俊文
× 慶祐, 俊文
|
|||||||
著者名(英) |
Toshifumi, Keiyuu
× Toshifumi, Keiyuu
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 最小費用流問題とは,「有向グラフG(V E)と各辺(i j)∈Eに対する単位フローあたりの非負整数コストc(i j),各辺に流すフロー上界値の非負整数容量u(i j)及び始点から終点に流す最大フローkが与えられたとき,流量がkでありかつ,各辺に流れるフローf(i j)とコストc(i j)の積の総和で求められるz(f)が最小であるフローfを求めよ」と定義される.本問題は輸送計画問題などに広く応用され,本問題を高速に解くことは重要である.本稿では,最小費用流問題における既存解法アルゴリズムの性能を計算機実験により評価を行い,RELAXが最も高速な解法であることを示す. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The minimum cost flow problem is defined by ``Given a directed network G(V,E) with a nonnegative integer cost c(i,j) and a nonnegative integer capacity u(i,j) associated with every arc (i,j)∈E, and a specified pair of vertices (a source s∈V and a sink t∈V) and having pair of the maximum flow value k, find a flow f of value k from s to t such that z(x) is minimum, where z(f) is the sum of the product f(i,j)・c(i,j) over all arcs (i,j) of a flow.''It is well recognized that the problem has wide application, such as the transportation problem for example, and devising efficient algorithms has been investigated so far. This paper compares performance of existing seven well-known algorithms haved on results by computer experiment. It is shown that RELAX or NETFLO gives the highest performance for dense networks or sparse over, respectively, among them. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 2006, 号 7(2006-AL-104), p. 67-74, 発行日 2006-01-20 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |