Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems

References

• Aggarwal A. , Bar-Noy A. , Coppersmith D. , Ramaswami R. , Schieber B. , Sudan M. Efficient routing in optical networks. J. ACM (1996) 46 973 1001 Crossref, Google Scholar
• Ahuja R. K. , Magnanti T. L. , Orlin J. B. Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Arora S. , Leighton F. T. , Maggs B. M. On-line algorithms for path selection in a nonblocking network. SIAM J. Comput. (1996) 25 600 625 Crossref, Google Scholar
• Aumann Y. , Rabani Y. Improved bounds for all-optical routing. Proc. ACM-SIAM Sympos. Discrete Algorithms (1995) (Society for Industrial and Applied Mathematics, San Francisco, CA) 567 576 Google Scholar
• Awerbuch B. , Gawlick R. , Leighton F. T. , Rabani Y. On-line admission control and circuit routing for high performance computing and communication. Proc. IEEE Sympos. Foundations Comput. Sci. (1994) (IEEE Computer Societry Press, Santa Fe, NM) 412 423 Crossref, Google Scholar
• Awerbuch B. , Leighton F. T. Improved approximations for the multi-commodity flow problem and local competitive routing in networks. Proc. ACM Sympos. Theory Comput. (ACM, Montreal, Quebec, Canada) 489 496 Google Scholar
• Boppana R. B. , Spencer J. H. A useful elementary correlation inequality. J. Combin. Theory, Ser. A (1989) 50 305 307 Crossref, Google Scholar
• Borkar S. , Cohn R. , Cox G. , Gleason S. , Gross T. , Kung H. T. , Lam M. , Moore B. , Peterson C. , Pieper J. , Rankin L. , Tseng P. S. , Sutton J. , Urbanski J. , Webb J. iWarp, an integrated solution to high-speed parallel computing. Proc. Internat. Sympos. Supercomput. (1988) (IEEE Computer Society and ACM Sigarch, Orlando, FL) 330 339 Crossref, Google Scholar
• Broder A. , Frieze A. , Upfal E. Existence and construction of edge-disjoint paths on expander graphs. SIAM J. Comput. (1994) 23 976 989 Crossref, Google Scholar
• Broder A. , Frieze A. , Upfal E. Static and dynamic path selection on expander graphs: A random walk approach. Random Structure Algorithms (1999) 14 87 109 Crossref, Google Scholar
• Cole R. J. , Maggs B. M. , Sitaraman R. K. Routing on butterfly networks with random faults. Proc. IEEE Sympos. Foundations Comput. Sci. (1995) (IEEE Computer Society Press, Milwaukee, WI) 558 570 Crossref, Google Scholar
• Erdös P. , Selfridge J. L. On a combinatorial game. J. Combin. Theory, Ser. A (1973) 14 298 301 Crossref, Google Scholar
• Fortuin C. M. , Ginibre J. , Kasteleyn P. N. Correlational inequalities for partially ordered sets. Comm. Math. Phys. (1971) 22 89 103 Crossref, Google Scholar
• Guruswami V. , Khanna S. , Rajaraman R. , Shepherd B. , Yannakakis M. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Proc. ACM Sympos. Theory Comput. (1999) (ACM, Atlanta, GA) 19 28 Crossref, Google Scholar
• Karp R. M. On the computational complexity of combinatorial problems. Networks (1975) 5 45 68 Crossref, Google Scholar
• Kleinberg J. Approximation algorithms for disjoint paths problems. (1996) . PhD Thesis, Department of EECS, MIT, Cambridge, MA Google Scholar
• Kleinberg J. , Rubinfeld R. Short paths in expander graphs. Proc. IEEE Sympos. Foundations Comput. Sci. (1996) (IEEE Computer Society Press, Burlington, VT) 86 95 Crossref, Google Scholar
• Kleinberg J. , Tardos É. Disjoint paths in densely embedded networks. Proc. IEEE Sympos. Foundations Comput. Sci. (1995) (IEEE Computer Society Press, Milwaukee, WI) 52 61 Google Scholar
• Kleinberg J. , Tardos É. Approximations for the disjoint paths problem in high-diameter planar networks. J. Comput. System Sci. (1998) 57 61 73 Crossref, Google Scholar
• Kolliopoulos S. G. , Stein C. Improved approximation algorithms for unsplittable flow problems. Proc. IEEE Sympos. Foundations Comput. Sci. (1997) (IEEE Computer Society Press, Miami Beach, FL) 426 435 Crossref, Google Scholar
• Kolliopoulos S. G. , Stein C. Approximating disjoint-path problems using greedy algorithms and packing integer programs. Proc. MPS Conference on Integer Programming and Combinatorial Optimization (1998) 1412 (Springer-Verlag, Houston, TX) 153 168 Lecture Notes in Computer Science Crossref, Google Scholar
• Leighton F. T. Introduction to Parallel Algorithms and Architectures: Arrays • Trees • Hypercubes. (1992) (Morgan Kaufmann, San Mateo, CA) Google Scholar
• Leighton F. T. , Maggs B. M. , Rao S. B. Packet routing and jobshop scheduling in O(congestion + dilation) steps. Combinatorica (1994) 14 167 186 Crossref, Google Scholar
• Leighton F. T. , Maggs B. M. , Richa A. Fast algorithms for finding O(congestion + dilation) packet routing schedules. (1996) . Technical Report CMU-CS-96-152, School of Computer Science, Carnegie-Mellon University, Pittsburgh, PA Google Scholar
• Leighton F. T. , Rao S. B. An approximate max-flow min-cut theorem for uniform multi-commodity flow problems with applications to approximation algorithms. Proc. IEEE Sympos. Foundations Comput. Sci. (1988) (IEEE Computer Society Press, White Plains, NY) 422 431 Google Scholar
• Leighton F. T. , Rao S. B. Circuit switching: A multi-commodity flow based approach. Proc. Workshop on Randomized Parallel Comput. (1996) Honolulu, HI 11 18 Google Scholar
• Lin J. H. , Vitter J. S. ε-approximations with minimum packing constraint violation. Proc. ACM Sympos. Theory Comput. (1992) (ACM, Victoria, BC, Canada) 771 782 Google Scholar
• Motwani R. , Naor J. , Raghavan P. , Hochbaum D. S. Randomized approximation algorithms in combinatorial optimization. Approximation Algorithms for NP-Hard Problems (1997) (PWS Press, Boston, MA) Google Scholar
• Motwani R. , Raghavan P. Randomized algorithms. (1995) (Cambridge University Press, Cambridge, UK) Google Scholar
• Noakes M. D. , Wallach D. A. , Dally W. J. The J-Machine multicomputer: An architectural evaluation. Proc. Ann. Internat. Sympos. Comput. Architecture (1993) (ACM, San Diego, CA) 224 235 Crossref, Google Scholar
• Peleg D. , Upfal E. Disjoint paths on expander graphs. Combinatorica (1989) 9 289 313 Crossref, Google Scholar
• Rabani Y. Path coloring on the mesh. Proc. IEEE Sympos. Foundations Comput. Sci. (1996) (IEEE Computer Society Press, Burlington, VT) 400 409 Crossref, Google Scholar
• Raghavan P. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. System Sci. (1988) 37 130 143 Crossref, Google Scholar
• Raghavan P. , Thompson C. D. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica (1987) 7 365 374 Crossref, Google Scholar
• Raghavan P. , Upfal E. Efficient all-optical routing. Proc. ACM Sympos. Theory Comput. (1994) (ACM, Montreal, Quebec, Canada) 134 143 Google Scholar
• Spencer J. H. Ten Lectures on the Probabilistic Method. (1987) (SIAM, Philadelphia, PA) Google Scholar
• Srinivasan A. Improved approximations of packing and covering problems. Proc. ACM Sympos. Theory Comput. (1995) (ACM, Las Vegas, NV) 268 276 Crossref, Google Scholar
• Srinivasan A. An extension of the Lovász Local Lemma, and its applications to integer programming. Proc. ACM-SIAM Sympos. Discrete Algorithms (1996) (SIAM, Atlanta, GA) 6 15 Google Scholar
• Upfal E. An O(log N) deterministic packet routing scheme. J. ACM (1992) 39 55 70 Crossref, Google Scholar