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

摘要

We present 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 the greedy algorithm for the maximum edge disjoint path problem. More precisely, our upper bound improves the approximation factor for this problem to O(n{sup}(3/4)).