On-line Algorithms: Proceedings of a DIMACS Workshop, February 11-13, 1991

Front Cover
Lyle A. McGeoch, Daniel Dominic Sleator
American Mathematical Soc., 1992 - Computers - 179 pages
This volume contains the proceedings of the Workshop on On-line Algorithms held at the DIMACS Center at Rutgers University in February 1991. Presenting new 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 consider alternative approaches. This book is aimed primarily at specialists in algorithm analysis, but most of the articles present clear expositions of previous work.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

The Server Problem and Online Games
2
The Harmonic Online KServer Algorithm is Competitive
65
The K Server Dual and Loose Competitiveness for Paging
77
Online Graph Coloring
85
Online Weighted Matching
93
Competitive Group Testing
125
Randomized Algorithms for Multiprocessor Page Migration
135
Navigating in Unfamiliar Geometric Terrain Extended Summary
151
Visual Searching and Mapping
157
Scheduling Parallel Machines Online
163
Lower Bounds for Online Graph Coloring
169
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information