## On-line Algorithms: Proceedings of a DIMACS Workshop, February 11-13, 1991This 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 |

### Other editions - View all

### Common terms and phrases

1992 American Mathematical amortized cost analysis binary tree Blue cost c-competitive CH(M Chrobak competitive algorithm competitive factor competitive ratio complete binary trees Computer Science Volume configuration conjecture consider defined denote deterministic algorithm distance eject Equipoise finite finite-cost follows game Q grandparent graph coloring graph G greedy algorithm group testing initial tree input interval graphs Kierstead left path Lemma lookahead lower bound Mathematics Subject Classification McGeoch memoryless metric space move multigraph multisets oblivious adversary offline server offset function on-line algorithm on-line coloring on-line games on-line graph on-line problems operation optimal partition pop path popped nodes potential function processor Proof prove pseudo-cost pure nodes randomized algorithm randomized on-line Red cost request sequence resetting right ancestors rithm robot rotations sequence of requests shaped sequence Sleator spanning tree splay trees strategy subset Tarjan Theorem Theoretical Computer Science tree player Union-Find Union-Find problem vertex vertices weighted