Preview
Unable to display preview. Download preview PDF.
References
H. Aborzi, E. Torng, P. Uthaisombut, and S. Wagner. The k-client problem. In Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 73–82, 1997.
M. Ajtai, J. Aspnes, C. Dwork, and O. Waarts. A theory of competitive analysis for distributed algorithms. In Proc. 35th Symp. of Foundations of Computer Science, pages 401–411, 1994.
M. Andrews, B. Awerbuch, A. Fernández, J. Kleinberg, T. Leighton, and Z. Liu. Universal stability results for greedy contention-resolution protocols. In Proc. 37th IEEE Symposium on Foundations of Computer Science, pages 380–389, 1996.
B. Awerbuch, Y. Bartal, and A. Fiat. Distributed paging for general networks. In Proceedings of the 7th Annual ACM-SIAM Symp. on Discrete Algorithms, pages 574–583, 1996.
Y. Azar, A. Broder, and M. Manasse. On-line choice of on-line algorithms. In Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, pages 432–440, 1993.
Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proc. 37th IEEE Symposium on Foundations of Computer Science, pages 184–193, 1996.
Y. Bartal, A. Blum, C. Burch, and A. Tomkins. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the 29th annual ACM symposium on theory of computing, pages 711–719, 1997.
Y. Bartal, M. Charikar, and P. Indyk. On page migration and other relaxed task systems. In Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 43–52, 1997.
A. Blum, H. Karloff, Y. Rabani, and M. Saks. A decomposition theorem and lower bounds for randomized server problems. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pages 197–207, 1992.
A. Blum, P. Raghavan, and B. Schieber. Navigating in unfamiliar geometric terrain. In Lyle A. McGeoch and Daniel D. Sleator, editors, On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 151–156. AMS/ACM, February 1991.
A. Borodin, S. Irani, P. Raghavan, and B. Schieber. Competitive paging with locality of reference. In Proc. 23rd ACM Symposium on Theory of Computing, pages 249–259, 1991.
A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D.P. Williamson. Adversarial queueing theory. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1997.
A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. In Proc. 19th Annual ACM Symposium on Theory of Computing, pages 373–382, 1987.
W.R. Burley and S. Irani. On algorithm design for metrical task systems. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 420–429, 1995.
M. Charikar, D. Halperin, and R. Motwani. The dynamic servers problem. In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 410–419, 1998.
X. Deng and C.H. Papadimitriou. Competitive distributed decision making. In International Federation for Infomation Processing, A-12, pages 250–256, 1992.
E. Feuerstein. On-line pagine of Structured Data and Multi-threaded Paging. PhD thesis, University of Rome, 1995.
A. Fiat, D. Foster, H. Karloff, Y. Rabani, Y. Ravid, and S. Vishwanathan. Competitive algorithms for layered graph traversal. In Proc. 32nd IEEE Symposium on Foundations of Computer Science, pages 288–297, 1991.
A. Fiat and M. Ricklin. Competitive algorithms for the weighted server problem. In Theoretical Computer Science, volume 130, pages 85–99, 1994.
S. Irani and Y. Rabani. On the value of information in coordination games. In Proc. 34th IEEE Symposium on Foundations of Computer Science, 1993.
S. Irani and Y. Rabani. On the value of coordination in distributed decision making. SIAM J. Comput., 25(3):498–519, 1996.
S. Irani and S.S. Seiden. Randomized algorithms for metrical task systems. Theoretical Computer Science, 194(1–2):163–182, March 1998.
B. Kalyanasundaram and K. Pruhs. Speed is as powerful as clairvoyance. In Proc. 36th IEEE Symposium on Foundations of Computer Science, pages 214–221, 1995.
A.R. Karlin, M.S. Manasse, L.A. McGeoch, and S. Owicki. Competitive randomized algorithms for non-uniform problems. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990.
H. Karloff, Y. Rabani, and Y. Ravid. Lower bounds for randomized k-server and motion planning algorithms. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 278–288, 1991.
E. Koutsoupias and C.H. Papadimitriou. Beyond competitive analysis. In Proc. 35th IEEE Symposium on Foundations of Computer Science, pages 394–400, 1994.
S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti, and A. Rosen. On-line randomized call control revisited. In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 323–332, 1998.
C. Lund and N. Reingold. Linear programs for randomized on-line algorithms. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 382–391, 1994.
R. Ostrovsky and Y. Rabani. Universal o(congenstion+dilation+log1+ε n) local control packet switching algorithms. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 644–653, 1997.
C.H. Papadimitriou and M. Yannakakis. Linear programming without the matrix. In Proc. 25th ACM Symposium on Theory of Computing, San Diego, pages 121–129, 1993.
C.A. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource augmentation. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 140–149, 1997.
Y. Rabani and E. Tardos. Distributed packet switching in arbitrary networks. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 366–367, 1996.
N.E. Young. On-line caching as cache size varies. In Proc. of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 241–250, 1991.
N.E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525–541, 1994.
N.E. Young. On-line file caching. In Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 82–86, 1998.
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Fiat, A., Woeginger, G.J. (1998). Competitive odds and ends. In: Fiat, A., Woeginger, G.J. (eds) Online Algorithms. Lecture Notes in Computer Science, vol 1442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029578
Download citation
DOI: https://doi.org/10.1007/BFb0029578
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64917-5
Online ISBN: 978-3-540-68311-7
eBook Packages: Springer Book Archive