Hardcover ISBN:  9780821865965 
Product Code:  DIMACS/7 
List Price:  $48.00 
MAA Member Price:  $43.20 
AMS Member Price:  $38.40 
eBook ISBN:  9781470439651 
Product Code:  DIMACS/7.E 
List Price:  $45.00 
MAA Member Price:  $40.50 
AMS Member Price:  $36.00 
Hardcover ISBN:  9780821865965 
eBook: ISBN:  9781470439651 
Product Code:  DIMACS/7.B 
List Price:  $93.00$70.50 
MAA Member Price:  $83.70$63.45 
AMS Member Price:  $74.40$56.40 
Hardcover ISBN:  9780821865965 
Product Code:  DIMACS/7 
List Price:  $48.00 
MAA Member Price:  $43.20 
AMS Member Price:  $38.40 
eBook ISBN:  9781470439651 
Product Code:  DIMACS/7.E 
List Price:  $45.00 
MAA Member Price:  $40.50 
AMS Member Price:  $36.00 
Hardcover ISBN:  9780821865965 
eBook ISBN:  9781470439651 
Product Code:  DIMACS/7.B 
List Price:  $93.00$70.50 
MAA Member Price:  $83.70$63.45 
AMS Member Price:  $74.40$56.40 

Book DetailsDIMACS  Series in Discrete Mathematics and Theoretical Computer ScienceVolume: 7; 1992; 179 ppMSC: Primary 05; 68; 90;
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.

Table of Contents

Chapters

A graphtheoretic game and its application to the $k$server problem (extended abstract)

The server problem and online games

The harmonic online $K$server algorithm is competitive

The $K$server dual and loose competitiveness for paging

A statistical adversary for online algorithms

Online graph coloring

Online weighted matching

On the competitiveness of splay trees: Relations to the unionfind problem

Competitive group testing

Randomized algorithms for multiprocessor page migration

Navigating in unfamiliar geometric terrain (extended summary)

Visual searching and mapping

Scheduling parallel machines online

Competitive paging with locality of reference (brief summary)

Lower bounds for online graph coloring


RequestsReview Copy – for publishers of book reviewsAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Requests
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.

Chapters

A graphtheoretic game and its application to the $k$server problem (extended abstract)

The server problem and online games

The harmonic online $K$server algorithm is competitive

The $K$server dual and loose competitiveness for paging

A statistical adversary for online algorithms

Online graph coloring

Online weighted matching

On the competitiveness of splay trees: Relations to the unionfind problem

Competitive group testing

Randomized algorithms for multiprocessor page migration

Navigating in unfamiliar geometric terrain (extended summary)

Visual searching and mapping

Scheduling parallel machines online

Competitive paging with locality of reference (brief summary)

Lower bounds for online graph coloring