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 |
| _version_ | 1826209737734094848 |
|---|---|
| author | Hajiaghayi, MohammadTaghi Leighton, F. Thomson |
| author2 | Theory of Computation |
| author_facet | Theory of Computation Hajiaghayi, MohammadTaghi Leighton, F. Thomson |
| author_sort | Hajiaghayi, MohammadTaghi |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T14:28:15Z |
| id | mit-1721.1/29829 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:28:15Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/298292019-04-12T13:39:27Z On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows Hajiaghayi, MohammadTaghi Leighton, F. Thomson Theory of Computation 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. 2005-12-12T23:22:48Z 2005-12-12T23:22:48Z 2003-07-05 MIT-CSAIL-TR-2003-002 MIT-LCS-TR-910 http://hdl.handle.net/1721.1/29829 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 5 p. 7867417 bytes 389570 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Hajiaghayi, MohammadTaghi Leighton, F. Thomson On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows |
| title | On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows |
| title_full | On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows |
| title_fullStr | On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows |
| title_full_unstemmed | On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows |
| title_short | On the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows |
| title_sort | on the max flow min cut ratio for directed multicommodity flows |
| url | http://hdl.handle.net/1721.1/29829 |
| work_keys_str_mv | AT hajiaghayimohammadtaghi onthemaxflowmincutratiofordirectedmulticommodityflows AT leightonfthomson onthemaxflowmincutratiofordirectedmulticommodityflows |