On the min-cut max-flow ratio for multicommodity flows

Oktay Gunluk (oktaywatson.ibm.com)

Abstract: In this paper we present a new bound on the min-cut max-flow ratio for multicommodity flow problems. We use a so-called aggregated commodity formulation and an optimal solution to its dual to show our main result. Currently, the best known bound for this ratio is proportional to log(k) where k is the number of origin-destination pairs with positive demand. We show a new ratio that is proportional to log(k*) where k* is the cardinality of the minimal vertex cover of the demand graph. We therefore relate the min-cut max-flow ratio of a multicommodity flow problem to the number of source nodes instead of the number of origin destination pairs. This result appears to be more natural since a generalization of the min-cut max-flow theorem holds tight for flow problems with a single source and multiple sink nodes. We also show a similar bound for the maximum multicommodity problem.

Keywords: multicommodity flows; min-cut max-flow; concurrent flow;

Category 1: Network Optimization

Citation: Technical Report, T. J. Watson Research Center.

Download: [Postscript]

Entry Submitted: 02/05/2001
Entry Accepted: 02/05/2001
Entry Last Modified: 02/05/2001

Modify/Update this entry