Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
| Title | Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems |
| Publication Type | Journal Articles |
| Year of Publication | 2000 |
| Authors | Baveja A, Srinivasan A |
| Journal | Mathematics of Operations ResearchMathematics of Operations Research |
| Volume | 25 |
| Issue | 2 |
| Pagination | 255 - 280 |
| Date Published | 2000/05/01/ |
| ISBN Number | 0364-765X, 1526-5471 |
| Keywords | Approximation algorithms, Disjoint paths, integer programming, Linear programming, multicommodity flow, Packing, randomized algorithms, rounding, Routing, unsplittable flow |
| Abstract | Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented. |
| URL | http://mor.journal.informs.org/content/25/2/255 |
| DOI | 10.1287/moor.25.2.255.12228 |