Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Edge-disjoint paths revisited

Edge-disjoint paths revisited The approximability of the maximum edge-disjoint paths problem (EDP) in directed graphs was seemingly settled by an Ω( m 1/2 − &epsis;)-hardness result of Guruswami et al. 2003, and an O (&sqrt; m ) approximation achievable via a natural multicommodity-flow-based LP relaxation as well as a greedy algorithm. Here m is the number of edges in the graph. We observe that the Ω( m 1/2 − &epsis;)-hardness of approximation applies to sparse graphs, and hence when expressed as a function of n , that is, the number of vertices, only an Ω( n 1/2 − &epsis;)-hardness follows. On the other hand, O (&sqrt; m )-approximation algorithms do not guarantee a sublinear (in terms of n ) approximation algorithm for dense graphs. We note that a similar gap exists in the known results on the integrality gap of the flow-based LP relaxation: an Ω(&sqrt; n ) lower bound and O (&sqrt; m ) upper bound. Motivated by this discrepancy in the upper and lower bounds, we study algorithms for EDP in directed and undirected graphs and obtain improved approximation ratios. We show that the greedy algorithm has an approximation ratio of O (min( n 2/3 , &sqrt; m )) in undirected graphs and a ratio of O (min( n 4/5 , &sqrt; m )) in directed graphs. For acyclic graphs we give an O (&sqrt; n ln n ) approximation via LP rounding. These are the first sublinear approximation ratios for EDP. The results also extend to EDP with weights and to the uniform-capacity unsplittable flow problem (UCUFP). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Edge-disjoint paths revisited

Download PDF
18 pages

Loading next page...
 
/lp/association-for-computing-machinery/edge-disjoint-paths-revisited-Ky5h6B17l9

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2007 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1290672.1290683
Publisher site
See Article on Publisher Site

Abstract

The approximability of the maximum edge-disjoint paths problem (EDP) in directed graphs was seemingly settled by an Ω( m 1/2 − &epsis;)-hardness result of Guruswami et al. 2003, and an O (&sqrt; m ) approximation achievable via a natural multicommodity-flow-based LP relaxation as well as a greedy algorithm. Here m is the number of edges in the graph. We observe that the Ω( m 1/2 − &epsis;)-hardness of approximation applies to sparse graphs, and hence when expressed as a function of n , that is, the number of vertices, only an Ω( n 1/2 − &epsis;)-hardness follows. On the other hand, O (&sqrt; m )-approximation algorithms do not guarantee a sublinear (in terms of n ) approximation algorithm for dense graphs. We note that a similar gap exists in the known results on the integrality gap of the flow-based LP relaxation: an Ω(&sqrt; n ) lower bound and O (&sqrt; m ) upper bound. Motivated by this discrepancy in the upper and lower bounds, we study algorithms for EDP in directed and undirected graphs and obtain improved approximation ratios. We show that the greedy algorithm has an approximation ratio of O (min( n 2/3 , &sqrt; m )) in undirected graphs and a ratio of O (min( n 4/5 , &sqrt; m )) in directed graphs. For acyclic graphs we give an O (&sqrt; n ln n ) approximation via LP rounding. These are the first sublinear approximation ratios for EDP. The results also extend to EDP with weights and to the uniform-capacity unsplittable flow problem (UCUFP).

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 1, 2007

There are no references for this article.