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.
Citation
Technical Report, T. J. Watson Research Center.