Preliminary versionA preliminary version of these results was presented in: James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 623-631, San Diego, California, 16-18 May 1993.
Categories and Subject Descriptors: C.2.1 [Computer-Communication Networks]: Network Architecture and Design; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
General Terms: Algorithms, Theory
Additional Key Words and Phrases: High-speed networks, on-line algorithms, optimization, routing
Selected references
- Baruch Awerbuch, Rainer Gawlick, Tom Leighton, and Yuval Rabani. On-line admission control and circuit routing for high performance computing and communication. In 35th Annual Symposium on Foundations of Computer Science, pages 412-423, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- Yossi Azar, Andrei Z. Broder, and Anna R. Karlin. On-line load balancing (extended abstract). In 33rd Annual Symposium on Foundations of Computer Science, pages 218-225, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Yossi Azar, Joseph Naor, and Raphael Rom. The competitiveness of on-line assignments. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 203-210, Orlando, Florida, 27-29 January 1992.
- Yair Bartal, Amos Fiat, Howard Karloff, and Rakesh Vohra. New algorithms for an ancient scheduling problem. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 51-58, Victoria, British Columbia, Canada, 4-6 May 1992.
- Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. Journal of the ACM, 39(4):745-763, October 1992.
- Anil Kamath, Omri Palmon, and Serge Plotkin. Routing and admission control in general topology networks with Poisson arrivals. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 269-278, Atlanta, Georgia, 28-30 January 1996.
- David Karger and Serge Plotkin. Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 18-25, Las Vegas, Nevada, 29 May-1 June 1995.
- Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel Dominic Sleator. Competitive snoopy caching. Algorithmica, 3:77-119, 1988.
- Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 352-358, Baltimore, Maryland, 14-16 May 1990.
- Jon Kleinberg and Éva Tardos. Disjoint paths in densely embedded graphs. In 36th Annual Symposium on Foundations of Computer Science, pages 52-61, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
- Philip Klein, Serge Plotkin, Clifford Stein, and Éva Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23(3):466-487, June 1994.
- Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Éva Tardos, and Spyros Tragoudas. Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50(2):228-243, April 1995.
- Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for on-line problems. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 322-333, Chicago, Illinois, 2-4 May 1988.
- Steven Phillips and Jeffery Westbrook. Online load balancing and network flow. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 402-411, San Diego, California, 16-18 May 1993.
- Farhad Shahrokhi and D. W. Matula. The maximum concurrent flow problem. Journal of the ACM, 37(2):318-334, April 1990.
- David B. Shmoys, Joel Wein, and David P. Williamson. Scheduling parallel machines on-line. In 32nd Annual Symposium on Foundations of Computer Science, pages 131-140, San Juan, Puerto Rico, 1-4 October 1991. IEEE.