著者

慶祐 俊文 高藤 大介 田岡 智志 渡邉 敏正

雑誌

情報処理学会研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2006, no.7(2006-AL-104), pp.67-74, 2006-01-20

---

最小費用流問題とは,「有向グラフG(V E)と各辺(i j)∈Eに対する単位フローあたりの非負整数コストc(i j),各辺に流すフロー上界値の非負整数容量u(i j)及び始点から終点に流す最大フローkが与えられたとき,流量がkでありかつ,各辺に流れるフローf(i j)とコストc(i j)の積の総和で求められるz(f)が最小であるフローfを求めよ」と定義される.本問題は輸送計画問題などに広く応用され,本問題を高速に解くことは重要である.本稿では,最小費用流問題における既存解法アルゴリズムの性能を計算機実験により評価を行い,RELAXが最も高速な解法であることを示す.