Literature

The Course Textbook

Allan Borodin, Ran El-Yaniv
Online Computation and Competitive Analysis
Cambridge University Press, 1998.

The book can be purchased in the university bookstore.

Errata etc. can be found via the book home page.

Further errors have been found while the course has been taught at SDU: Errata 1, Errata 2.

Additional obligatory material

The Relative Worst Order Ratio Applied to Paging.

Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
Journal of Computer and System Sciences, 73(5): 818-843, 2007.
The publication is available from ScienceDirect
(students can obtain this publication at no cost by being logged in on an SDU computer; contact Kim S. Larsen if there are problems with this)

Slides from lectures

• On Paging and Relative Worst Order Analysis

Supplementary material

• Susanne Albers' lecture notes (BRICS lecture series, number LS-96-2).
• Michel Goemans' course notes.