LCS Publication Details
Publication Title: On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows
Publication Author: Hajiaghayi, MohammadTaghi
Additional Authors: F. Thomson Leighton
LCS Document Number: MIT-LCS-TR-910
Publication Date: 7-5-2003
LCS Group: Theory of Computation
Additional URL:
Abstract:
We give a pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows. In addition, this combinatorial problem has applications in improving the approximation factor of Greedy algorithm for maximum edge disjoint path problem. More precisely, our upper bound improves the approximation factor for this problem to O(n^{3/4}). Finally, we demonstrate how even for very simple graphs the aforementioned ratio might be very large.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.