**DIMACS - Series in Discrete Mathematics and Theoretical Computer Science**

Volume: 7;
1992;
179 pp;
Hardcover

MSC: Primary 05; 68; 90;

Print ISBN: 978-0-8218-6596-5

Product Code: DIMACS/7

List Price: $42.00

Individual Member Price: $33.60

**Electronic ISBN: 978-1-4704-3965-1
Product Code: DIMACS/7.E**

List Price: $42.00

Individual Member Price: $33.60

# On-line Algorithms

Share this page *Edited by *
*Lyle A. McGeoch; Daniel D. Sleator*

A co-publication of the AMS, DIMACS, and Association for Computing Machinery

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.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

# Table of Contents

## On-line Algorithms

- Cover Cover11
- Title page iii4
- Foreword v6
- Preface vii8
- Contents ix10
- List of participants xi12
- A graph-theoretic game and its application to the 𝑘-server problem (extended abstract) 114
- The server problem and on-line games 1124
- The harmonic online 𝐾-server algorithm is competitive 6578
- The 𝐾-server dual and loose competitiveness for paging 7790
- A statistical adversary for on-line algorithms 7992
- On-line graph coloring 8598
- Online weighted matching 93106
- On the competitiveness of splay trees: Relations to the union-find problem 95108
- Competitive group testing 125138
- Randomized algorithms for multiprocessor page migration 135148
- Navigating in unfamiliar geometric terrain (extended summary) 151164
- Visual searching and mapping 157170
- Scheduling parallel machines on-line 163176
- Competitive paging with locality of reference (brief summary) 167180
- Lower bounds for on-line graph coloring 169182
- Back Cover Back Cover1193