Selected papers that cite this one
- Houman Alborzi, Eric Torng, Patchrawat Uthaisombut, and Stephen Wagner. The k-client problem. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 73-82, New Orleans, Louisiana, 5-7 January 1997.
- Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78-100, February 1995.
- James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM, 44(3):486-504, May 1997.
- Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R. Pruhs, and Orli Waarts. On-line load balancing of temporary tasks. Journal of Algorithms, 22(1):93-110, January 1997.
- Ran Bachrach and Ran El-Yaniv. Online list accessing algorithms and their applications: Recent empirical evidence. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 53-62, New Orleans, Louisiana, 5-7 January 1997.
- Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 711-719, El Paso, Texas, 4-6 May 1997.
- Allan Borodin and Ran El-Yaniv. On randomization in online computation. Accepted for publication in Information and Computation. Final manuscript received for publication November 2, 1998.
- William R. Burley. Traversing layered graphs using the work function algorithm. Journal of Algorithms, 20(3):479-511, May 1996.
- Tyng-Ruey Chuang and Wen L. Hwang. A probabilistic approach to the problem of automatic selection of data representations. In Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming, pages 190-200, Philadelphia, Pennsylvania, 24-26 May 1996.
- Xiaotie Deng and Sanjeev Mahajan. The cost of derandomization: Computability or competitiveness. SIAM Journal on Computing, 26(3):786-802, June 1997.
- Sandy Irani and Yuval Rabani. On the value of coordination in distributed decision making. SIAM Journal on Computing, 25(3):498-519, June 1996.
- Sandy Irani and Steve Seiden. Randomized algorithms for metrical task systems. Theoretical Computer Science, 194(1-2):163-182, 10 March 1998.
- Anil Kamath, Omri Palmon, and Serge Plotkin. Routing and admission control in general topology networks with Poisson arrivals. Journal of Algorithms, 27(2):236-258, May 1998.
- Yuan Ma and Serge Plotkin. An improved lower bound for load balancing of tasks with unknown duration. Information Processing Letters, 62(6):301-303, 27 June 1997.
- H. Ramesh. On traversing layered graphs on-line. Journal of Algorithms, 18(3):480-512, May 1995.
- Steven Seiden. Unfair problems and randomized algorithms for metrical task systems. Accepted for publication in Information and Computation. Final manuscript received for publication May 31, 1998, 1998.
- Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1-2):343-359, 20 May 1996. Mathematical Games.
Selected references
- S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson. On the power of randomization in online algorithms (extended abstract). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 379-386, Baltimore, Maryland, 14-16 May 1990.
- Don Coppersmith, Peter Doyle, Prabhakar Raghavan, and Marc Snir. Random walks on weighted graphs, and applications to on-line algorithms (preliminary version). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 369-378, Baltimore, Maryland, 14-16 May 1990.
- Amos Fiat, Yuval Rabani, and Yiftach Ravid. Competitive k-server algorithms (extended abstract). In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 454-463, St. Louis, Missouri, 22-24 October 1990. IEEE.
- E. F. Grove. The harmonic online K-server algorithm is competitive. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 260-266, New Orleans, Louisiana, 6-8 May 1991.
- Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, pages 222-227, Providence, Rhode Island, 31 October-2 November 1977. IEEE.