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.
Entry Submitted: 02/05/2001
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|