多物網絡流問題

维基百科，自由的百科全书

多物網絡流問題 (Multi-commodity Flow Problem)是多種物品（或貨物）在網絡中從不同的源點流向不同的匯點的網絡流問題。

[编辑] 定義

已知一流網絡 $\,G(V,E)$ ，其中邊 $(u,v) \in E$ 的容量為 $\,c(u,v)$ 。有 $\,k$ 件物品 $K_1,K_2,\dots,K_k$ ，定義為 $\,K_i=(s_i,t_i,d_i)$ ，其中 $\,s_i$ 和 $\,t_i$ 是物品 $\,i$ 的源點及匯點，及 $\,d_i$ 是需求。物品 $\,i$ 沿邊 $\,(u,v)$ 的流量是 $\,f_i(u,v)$ 。求一個符合以下限制的流量分配：

容量限制:	$\,\sum_{i=1}^{k} f_i(u,v) \leq c(u,v)$
流守恆:	$\,\sum_{w \in V} f_i(u,w) = 0 \quad \mathrm{when} \quad u \neq s_i, t_i$
需求的滿足:	$\,\sum_{w \in V} f_i(s_i,w) = d_i \Leftrightarrow \sum_{w \in V} f_i(w,t_i) = d_i$

在最小成本多物網絡流問題中，在 $\,(u,v)$ 上傳送需要成本 $a(u,v) \cdot f(u,v)$ 。目的是要最小化

$\sum_{(u,v) \in E} \left( a(u,v) \sum_{i=1}^{k} f_i(u,v) \right)$

在最大多物網絡流問題中，每件物品都沒有硬性的需求，但最大化總生產量：

$\sum_{i=1}^{k} \sum_{w \in V} f_i(s_i,w)$

在最大同時網絡流問題中，任務是要將物品的流量對它的需求的最小比例最大化：

$\min_{1 \leq i \leq k} \frac{\sum_{w \in V} f_i(s_i,w)}{d_i}$

[编辑] 與其它問題的關係

最小成本變體是普遍化的最小成本網絡流問題。環流問題的變體是所有網絡流問題的概括。

[编辑] 用途

利用多物網絡流的公式可以接近在光學網絡的光學群聚交換中的路由波長分配 (RWA, Routing Wavelength Assignment)。

[编辑] 解

這問題已知的解是建基於線性規劃^[1].

就算只有兩件物品，對於整體流來說，這問題是NP完全^[2]。在有錯誤限下，已有完全多項式時間近似值的方法去解決這難題^[3]。對於這難題的分數變體，在多項式時間中已有解。

[编辑] 參考

↑ Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 和 Clifford Stein [1990] (2001). "29"， Introduction to Algorithms，2nd edition, 788-789，MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
↑ S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing 5: 691-703. DOI:10.1137/0205048.
↑ George Karakostas （2002）。 Faster approximation schemes for fractional multicommodity flow problems。 Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms， 166--173。