APPROXIMATE MAX-FLOW MIN-(MULTI)CUT THEOREMS AND THEIR APPLICATIONS

Consider the multicommodity flow problem in which the object is to max imize the sum of commodities routed. We prove the following approximat e max-flow min-multicut theorem: [GRAPHICS] where k is the number of c ommodities. Our proof is constructive; it enables us to find a multicu t within O(log k) of the max flow (and hence also the optimal multicut ). In addition, the proof technique provides a unified framework in wh ich one can also analyse the case of flows with specified demands of L eighton and Rao and Klein et al. and thereby obtain an improved bound for the latter problem.