Online Algorithms: The State of the Art

Amos Fiat, Gerhard J. Woeginger (auth.), Amos Fiat, Gerhard J. Woeginger (eds.)3540649174, 9783540649175

This coherent anthology presents the state of the art in the booming area of online algorithms and competitive analysis of such algorithms. The 17 papers are carefully revised and thoroughly improved versions of presentations given first during a Dagstuhl seminar in 1996.
An overview by the volume editors introduces the area to the reader. The technical chapters are devoted to foundational and methodological issues for the design and analysis of various classes of online algorithms as well as to the detailed evaluation of algorithms for various activities in online processing, ranging from load balancing and scheduling to networking and financial problems. An outlook by the volume editors and a bibliography listing more than 750 references complete the work.
The book is ideally suited for advanced courses and self-study in online algorithms. It is indispensable reading for researchers and professionals active in the area.

---

Table of contents :
Competitive analysis of algorithms….Pages 1-12
Self-organizing data structures….Pages 13-51
Competitive analysis of paging….Pages 52-73
Metrical task systems, the server problem and the work function algorithm….Pages 74-96
Distributed paging….Pages 97-117
Competitive analysis of distributed algorithms….Pages 118-146
On-line packing and covering problems….Pages 147-177
On-line load balancing….Pages 178-195
On-line scheduling….Pages 196-231
On-line searching and navigation….Pages 232-241
On-line network routing….Pages 242-267
On-line network optimization problems….Pages 268-280
Coloring graphs on-line….Pages 281-305
On-Line Algorithms in Machine Learning….Pages 306-325
Competitive solutions for on-line financial problems….Pages 326-372
On the performance of competitive algorithms in practice….Pages 373-384
Competitive odds and ends….Pages 385-394