Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
作者： Alok Baveja , Aravind Srinivasan
DOI: 10.1287/MOOR.25.2.255.12228
关键词:
摘要: Given a network and set of connection requests on it, we consider the maximum edge-disjoint paths related generalizations routing problems that arise in assigning for these requests. We present improved approximation algorithms and/or integrality gaps all considered; central theme this work is underlying multicommodity flow relaxation. Applications techniques to approximating families packing integer programs are also presented.
core.ac.uk
acm.org
jstor.org 
sci-hub.se 参考文章(39)
R. M. Karp, On the Computational Complexity of Combinatorial Problems Networks. ,vol. 5, pp. 45- 68 ,(1975) , 10.1002/NET.1975.5.1.45
Jeffrey S Vitter, Jyh Lin, Approximations with Minimum Packing Constraint Violation ,(1992)
Joel Spencer, Ten lectures on the probabilistic method ,(1987)
Stavros G. Kolliopoulos, Clifford Stein, Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs integer programming and combinatorial optimization. pp. 153- 168 ,(1997) , 10.1007/3-540-69346-7_12
Michel X. Goemans, Jon Michael Kleinberg, Approximation algorithms for disjoint paths problems Massachusetts Institute of Technology. ,(1996)
S.G. Kolliopoulos, C. Stein, Improved approximation algorithms for unsplittable flow problems foundations of computer science. pp. 426- 436 ,(1997) , 10.1109/SFCS.1997.646131
James B. Orlin, Thomas L. Magnanti, Ravindra K. Ahuja, Network Flows: Theory, Algorithms, and Applications ,(1993)
Dorit S. Hochba, Approximation Algorithms for NP-Hard Problems ,(1996)
Jyh-Han Lin, Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract) symposium on the theory of computing. pp. 771- 782 ,(1992) , 10.1145/129712.129787
Ravi Boppona, Joel Spencer, A Useful Elementary Correlation Inequality, II Journal of Combinatorial Theory, Series A. ,vol. 50, pp. 305- 307 ,(1989) , 10.1016/0097-3165(89)90022-8