DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME SEVEN
TITLE: "ON-LINE ALGORITHMS"
EDITORS: Lyle A. McGeoch and Daniel D. Sleator
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE

The DIMACS Workshop on On-Line Algorithms was held February 11-13, 1991 at Rutgers University. There were 81 participants, including 22 students. The program featured 16 scheduled talks, six informal presentations, and a concluding panel discussion. this volume contains an abstract or paper for most of the scheduled talks.

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.

TABLE OF CONTENTS




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
Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.