Flows in dynamic networks with aggregate arc capacities

Vardges Melkonian
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 30-35
http://dx.doi.org/10.1016/j.ipl.2006.07.007

動的transshipment problemといえば，Hoppe and Tardos (2000) の結果が有名で，多項式時間で解けることが知られているが，この論文ではcapacityに通常の動的流問題と異なる解釈を与えたバージョンでtransshipment problemを考えている．
通常の解釈では，capacityというのは単位時間に辺へ流れ込むフローの上界である．
しかし，この論文の解釈ではcapacityを任意の時刻で辺に滞留しているフロー量の上界とするのである．
(応用としては「橋」のようなものを思いつかべればよい，と論文に書いてある．)
このバージョンではtransshipment問題がNP完全になることを証明している．
またtime-expanded networkを用いた線型計画問題としての定式化も与え，それを用いれば擬多項式時間アルゴリズムが得られる．