Fiat A., Woeginger G.J. (eds.) Online Algorithms. The State of the Art

Springer, 1998, -455 p.A workshop on the competitive analysis of on-line algorithms was held at Schloss Dagstuhl (Germany) during the last week of June 1996. Many survey talks were presented at this workshop. We then asked the speakers to prepare survey chapters that covered and extended the contents of their talks. This volume now is the compilation of the survey chapters. We thank all contributors who so generously gave of their time to make the book a success.Competitive Analysis of Algorithms
Self-Organizing Data Structures
Competitive Analysis of Paging
Metrical Task Systems, the Server Problem and the Work Function Algorithm
Distributed Paging
Competitive Analysis of Distributed Algorithms
On-line Packing and Covering Problems
On-line Load Balancing
On-Line Scheduling
On-line Searching and Navigation
On-line Network Routing
On-line Network Optimization Problems
Coloring Graphs On-Line
On-Line Algorithms in Machine Learning
Competitive Solutions for On-line Financial Problems
On the Performance of Competitive Algorithms in Practice
Competitive Odds and Ends