Approximate max-flow min-(multi)cut theorems and their applications
Approximate max-flow min-(multi)cut theorems and their applications
复制标题
DOI：
10.1145/167088.167266
复制
发表时间：
1993-06
期刊：
影响因子：
--
通讯作者：
Naveen Garg;V. Vazirani;M. Yannakakis
中科院分区：
文献类型：
--
作者：
Naveen Garg;V. Vazirani;M. Yannakakis
考虑多商品流问题，其目标是最大化所选路线的商品之和。我们证明了以下近似的最大流最小多割定理：$$ \dst \frac{\mbox{\rm min multicut}}{O（\log k）} \leq\mbox{\rm max flow } \leq\mbox{ \rm min multicut}，$$ \numerical其中$k$是商品的数量。我们的证明是建设性的;它使我们能够找到一个多割内$O（\log k）$的最大流（因此也是最优的多割）。此外，证明技术提供了一个统一的框架，其中也可以分析的情况下，流与指定的需求的莱顿和饶和克莱因等人。从而获得一个改进的边界后一个问题。
Consider the multicommodity flow problem in which the object is to maximize the sum of commodities routed. We prove the following approximate max-flow min-multicut theorem: $$ \dst \frac{\mbox{\rm min multicut}}{O(\log k)} \leq \mbox{ \rm max flow } \leq \mbox{ \rm min multicut}, $$ \noindent where $k$ is the number of commodities. Our proof is constructive; it enables us to find a multicut within $O(\log k)$ of the max flow (and hence also the optimal multicut). In addition, the proof technique provides a unified framework in which one can also analyse the case of flows with specified demands of Leighton and Rao and Klein et al. and thereby obtain an improved bound for the latter problem.