Approximate max-flow min-(multi)cut theorems and their applications

Garg, Naveen ; Vazirani, Vijay V. ; Yannakakis, Mihalis (1996) Approximate max-flow min-(multi)cut theorems and their applications SIAM Journal on Computing, 25 (2). pp. 235-251. ISSN 0097-5397

Full text not available from this repository.

Official URL:

Related URL:


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: \[ \frac{{\min {\text{multicut}}}}{{O(\log k)}} \leqslant \max {\text{flow}} \leqslant \min {\text{multicut}}, \] 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 analyze 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.

Item Type:Article
Source:Copyright of this article belongs to Society for Industrial & Applied Mathematics.
ID Code:101273
Deposited On:31 Jan 2018 09:33
Last Modified:31 Jan 2018 09:33

Repository Staff Only: item control page