To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
A high point of the workshop was the panel discussion, which featured Richard Karp, Larry Larmore, Mark Manasse, Prabhakar Raghavan, and Daniel Sleator. Unfortunately we did not record the discussion, because a transcript would have been a useful addition to this volume. The panel considered the interaction between the theory and practice of on-line algorithms. Competitive analysis, while being a useful mathematical tool, sometimes yields bounds that are unduly pessimistic. It was agreed that it is worthwhile to consider other approaches to evaluating on-line algorithms, such as those discussed in "A statistical adversary for on-line algorithms" and "Competitive paging with locality of reference". The panel was encouraged by the variety of new problems (such as navigation, the testing of groups, and the evaluation of investment strategies) where on-line analysis is being applied.
We received many positive responses from the participants in the workshop, and we are deeply indebted to DIMACS for giving us the opportunity to organize it. Daniel Gorenstein, Fred Roberts, Bob Tarjan, Carol Rusnak, and Pat Toci all helped us greatly. We would also like to thank Donna Harmon and Christine Turgeon at AMS for helping prepare this volume.
List of Participants xi A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract) Noga Alon, Richard M. Karp, David Peleg, and Douglas West 1 The Server Problem and On-Line Games Marek Chrobak and Lawrence L. Larmore 11 The Harmonic Online K-Server Algorithm in Competitive E.F. Grove 65 The K-Server Dual and Loose Competitiveness for Paging Neal Young 77 A Statistical Adversary for On-line Algorithms Prabhakar Raghavan 79 On-line Graph Coloring H.A. Kierstead and W.T. Trotter 85 Online Weighted Matching Bala Kalyanasundaram and Kirk Pruhs 93 On the Competitiveness of Splay Trees: Relations to the Union-Find Problem Joan M. Lucas 95 Competitive Group Testing D.Z. Du and F. K. Hwang 125 Randomized Algorithms for Multiprocessor Page Migration Jeffery Westbrook 135 Navigating in Unfamiliar Geometric Terrain (Extended Summary) Avrim Blum, Prabhakar Raghavan, and Baruch Schieber 151 Visual Searching and Mapping Bala Kalyanasundaram and Kirk Pruhs 157 Scheduling Parallel Machines On-line David B. Shmoys, Joel Wein, and David P. Williamson 163 Competitive Paging with Locality of Reference (Brief Summary) Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber 167 Lower Bounds for On-line Graph Coloring Magnus M. Halldorsson and Marion Szegedy 169