  


On the mincut maxflow ratio for multicommodity flows
Oktay Gunluk (oktaywatson.ibm.com) Abstract: In this paper we present a new bound on the mincut maxflow ratio for multicommodity flow problems. We use a socalled 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 origindestination 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 mincut maxflow 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 mincut maxflow 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; mincut maxflow; concurrent flow; Category 1: Network Optimization Citation: Technical Report, T. J. Watson Research Center. Download: [Postscript] Entry Submitted: 02/05/2001 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  