On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows
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 upp...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/29829 |
| Summary: | 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. |
|---|