Simple on-line algorithms for the maximum disjoint paths problem

ABSTRACT

In this paper we study the problem of finding disjoint paths in graphs. Whereas for specific graphs many (almost) matching upper and lower bounds are known for the competitiveness of on-line path selection algorithms, much less is known about how well on-line algorithms can perform in the general setting. In several papers the expansion has been used to measure the performance of off-line and on-line algorithms in this field. We study a class of simple deterministic on-line algorithms and show that they achieve a competitive ratio that is asymptotically equal to the best possible competitive ratio that can be achieved by any deterministic on-line algorithm. For this we use a parameter caled routing number which allows more precise results than the expansion. Interestingly, our upper bound on the competitive ratio is even better than the best approximation ratio known for off-line algorithms. Furthermore, we show that a refined variant of the routing number allows to construct on-line algorithms with a competitive ratio that is for many graphs significantly below the best possible upper bound for deterministic on-line algorithms if only the routing number or expansion of a graph is known. We also show that our algorithms can be transformed into efficient algorithms for the related unsplittable flow problem.

References

1. 1.Y. Aumann and Y. Rabani. Improved bounds for all optical routing. In Proceedings of the 6th Annual Symposium on Discrete Algorithms, pages 567-576, New York, NY, USA, Jan. 1995. ACM Press.]]
2. 2.B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive on-line routing. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pages 32-40, Palo Alto, California, 3-5 Nov. 1993. IEEE.]]
3. 3.B. Awerbuch, Y. Bartal, A. Fiat, and A. Rosen. Competitive non-preemptive call control. Manuscript, 1993.]]
4. 4.B. Awerbuch, Y. Bartal, A. Fiat, and A. Rosen. Competitive non-preemptive call control. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, pages 312-320, 1994.]]
5. 5.B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 412-423, 1994.]]
6. 6.Y. Azar and O. Regev. Strongly polynomial algorithms for the unsplittable ow problem. In IPCO: 8th Integer Programming and Combinatorial Optimization Conference, Lecture Notes in Computer Science, 2001.]]
7. 7.Y. Bartal, A. Fiat, and S. Leonardi. Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pages 531-540, Philadelphia, Pennsylvania, 22-24 May 1996.]]
8. 8.A. Baveja and A. Srinivasan. Approximation algorithms for disjoint paths and related routing and packing problems. MOR: Mathematics of Operations Research, 25, 2000.]]
9. 9.A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.]]
10. 10.A. Z. Broder, A. M. Frieze, and E. Upfal. Existence and construction of edge-disjoint paths on expander graphs. SIAM Journal on Computing, 23(5):976-989, Oct. 1994.]]
11. 11.A. Z. Broder, A. M. Frieze, and E. Upfal. Static and dynamic path selection on expander graphs: A random walk approach (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 531-539, 4-6 May 1997.]]
12. 12.A. Z. Broder, A. M. Frieze, and E. Upfal. Static and dynamic path selection on expander graphs: A random walk approach. RSA: Random Structures & Algorithms, 14, 1999.]]
13. 13.A. M. Frieze. Disjoint paths in expander graphs via random walks: A short survey. InRANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science. LNCS, 1998.]]
14. 14.J. A. Garay, I. S. Gopal, S. Kutten, Y. Mansour, and M. Yung. Efficient on-line call control algorithms. In Proceedings of the 2nd Israeli Symposium on Theory of Computing and Systems, pages 285-293, 1993.]]
15. 15.J. A. Garay, I. S. Gopal, S. Kutten, Y. Mansour, and M. Yung. Efficient on-line call control algorithms. J. Algorithms, 23(1):180-194, 1997.]]
16. 16.V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis. Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. In Proc. 31st ACM Symp. on Theory of Computing, pages 19-28, 1999.]]
17. 17.R. M. Karp. On the computational complexity of combinatorial problems. Networks, 5(9):45-68, 1975.]]
18. 18.J. Kleinberg. Approximation Algorithms for Disjoint Paths Problems. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1996.]]
19. 19.J. Kleinberg and R. Rubinfeld. Short paths in expander graphs. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 86-95, 1996.]]
20. 20.J. Kleinberg and E. Tardos. Disjoint paths in densely embedded graphs. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 52-61, Los Alamitos, Oct. 1995. IEEE Computer Society Press.]]
21. 21.J. Kleinberg and E. Tardos. Approximations for the disjoint paths probelm in high-diameter planar networks. Journal of Computer and System Sciences, 57(1):61-73, Aug. 1998.]]
22. 22.S. G. Kolliopoulos and C. Stein. Approximating disjoint-path problems using greedy algorithms and packing integer programs. In IPCO: 6th Integer Programming and Combinatorial Optimization Conference, volume 1412 of Lecture Notes in Computer Science, pages 153-162, 1998.]]
23. 23.P. Kolman. Short disjoint paths on hypercubic graphs. Technical Report 2000-481, Charles University, KAM-DIMATIA Series, 2000. Submitted to Journal of Interconnection Networks.]]
24. 24.P. Kolman and C. Scheideler. Simple on-line algorithms for the maximum disjoint paths problem. Technical report, http://www.cs.jhu.edu/~scheideler, 2000.]]
25. 25.T. Leighton and S. Rao. An approximate max- ow min-cut theorem for uniform multicommodity ow problems with applications to approximation algorithms. In 29th Annual Symposium on Foundations of Computer Science, pages 422-431, White Plains, New York, 24-26 Oct. 1988. IEEE.]]
26. 26.T. Leighton and S. Rao. Multicommodity max- ow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787-832, Nov. 1999.]]
27. 27.S. Leonardi. On-line network routing. In G. J. W. Amos Fiat, editor, Online Alogithms, volume 1442 of Lecture Notes in Computer Science, pages 242-267. Springer, 1998.]]
28. 28.S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti, and A. Rosen. On-line randomized call control revisited. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 323-332, San Francisco, California, 25-27 Jan. 1998.]]
29. 29.D. Peleg and E. Upfal. Constructing disjoint paths on expander graphs. COMBINAT: Combinatorica, 9, 1989.]]
30. 30.P. Raghavan and C. D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365-374, 1987.]]
31. 31.C. Scheideler. Universal Routing Strategies for Interconnection Networks. Lecture Notes in Computer Science 1390, Springer Verlag, 1998.]]
32. 32.D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, Feb. 1985.]]
33. 33.A. Srinivasan. Improved approximations for edge-disjoint paths, unsplittable ow, and related routing problems. In 38th Annual Symposium on Foundations of Computer Science, pages 416-425, 20-22 Oct. 1997.]]
34. 34.A. Srinivasan. A survey of the role of multicommodity ow and randomization in network and routing. In S. R. P. Pardalos and J. Rolim, editors, Randomization Methods in Algorithm Design, volume 43 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science., pages 271-302. American Mathematical Society, June 1999.]]
35. 35.V. G. Vizing. On an estimate of the chromatic class of a p-graph (in russian). Diskret. Analiz, 3:23-30, 1964.]]

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Paths and connectivity problems

• Theory of computation

  • Design and analysis of algorithms