DIMACS: Series in Discrete Mathematics and Theoretical Computer Science 1992; 179 pp; hardcover Volume: 7 ISBN10: 082186596X ISBN13: 9780821865965 List Price: US$40 Member Price: US$32 Order Code: DIMACS/7
 This volume contains the proceedings of the Workshop on Online Algorithms held at the DIMACS Center at Rutgers University in February 1991. Presenting results in the theory of online algorithms, the articles discuss a broad range of problems. Most of the papers are based on competitive (worstcase) analysis of online algorithms, but some papers consider alternative approaches to online analysis. A critical question examined by some of the authors is how to modify competitive analysis to better reconcile the theory and practice of online 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. Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 17 were copublished with the Association for Computer Machinery (ACM). Table of Contents  N. Alon, R. M. Karp, D. Peleg, and D. West  A graphtheoretic game and its application to the \(k\)server problem (extended abstract)
 M. Chrobak and L. L. Larmore  The server problem and online games
 E. F. Grove  The harmonic online \(K\)server algorithm is competitive
 N. Young  The \(K\)server dual and loose competitiveness for paging
 P. Raghavan  A statistical adversary for online algorithms
 H. A. Kierstead and W. T. Trotter  Online graph coloring
 B. Kalyanasundaram and K. Pruhs  Online weighted matching
 J. M. Lucas  On the competitiveness of splay trees: Relations to the unionfind problem
 D. Z. Du and F. K. Hwang  Competitive group testing
 J. Westbrook  Randomized algorithms for multiprocessor page migration
 A. Blum, P. Raghavan, and B. Schieber  Navigating in unfamiliar geometric terrain (extended summary)
 B. Kalyanasundaram and K. Pruhs  Visual searching and mapping
 D. B. Shmoys, J. Wein, and D. P. Williamson  Scheduling parallel machines online
 A. Borodin, S. Irani, P. Raghavan, and B. Schieber  Competitive paging with locality of reference (brief summary)
 M. M. Halldórsson and M. Szegedy  Lower bounds for online graph coloring
