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

Supplementary material

This material is not part of the official curriculum. Use it if you find it helpful.

Last modified: Fri Sep 17 14:13:52 CEST 2010
Kim Skak Larsen (