This volume contains the proceedings of the Workshop on On-line Algorithms held at the DIMACS Center at Rutgers University in February 1991. Presenting results in the theory of on-line algorithms, the articles discuss a broad range of problems. Most of the papers are based on competitive (worst-case) analysis of on-line algorithms, but some papers consider alternative approaches to on-line analysis. A critical question examined by some of the authors is how to modify competitive analysis to better reconcile the theory and practice of on-line algorithms. Many of the papers examine the ways in which randomization can be used to yield algorithms with improved performance. This book is aimed primarily at specialists in algorithm analysis, but most of the articles present clear expositions of previous work.
A graph-theoretic game and its application to the $k$-server problem (extended abstract) by N. Alon, R. M. Karp, D. Peleg, and D. West The server problem and on-line games by M. Chrobak and L. L. Larmore The harmonic online $K$-server algorithm is competitive by E. F. Grove The $K$-server dual and loose competitiveness for paging by N. Young A statistical adversary for on-line algorithms by P. Raghavan On-line graph coloring by H. A. Kierstead and W. T. Trotter Online weighted matching by B. Kalyanasundaram and K. Pruhs On the competitiveness of splay trees: Relations to the union-find problem by J. M. Lucas Competitive group testing by D. Z. Du and F. K. Hwang Randomized algorithms for multiprocessor page migration by J. Westbrook Navigating in unfamiliar geometric terrain (extended summary) by A. Blum, P. Raghavan, and B. Schieber Visual searching and mapping by B. Kalyanasundaram and K. Pruhs Scheduling parallel machines on-line by D. B. Shmoys, J. Wein, and D. P. Williamson Competitive paging with locality of reference (brief summary) by A. Borodin, S. Irani, P. Raghavan, and B. Schieber Lower bounds for on-line graph coloring by M. M. Halldorsson and M. Szegedy.