On-Line Algorithms


The course will be held in the seminar room.


A course description.

The textbook:

Online Computation and Competitive Analysis, by Borodin and El-Yaniv. There will also be notes.
There is a homepage for the textbook, including errata list.
Further errata found by students who took this course earlier.


The exam questions are here (and also in PDF).

Weekly notes

  1. Note 1 (also in PDF).
  2. Note 2 (also in PDF).
  3. Note 3 (also in PDF).
  4. Note 4 (also in PDF).
  5. Note 5 (also in PDF).
  6. Note 6 (also in PDF). Exercises 6.5 and 6.6 will be postponed until next week.
  7. Note 7 (also in PDF).
  8. Note 8 (also in PDF).
  9. Note 9 (also in PDF).
  10. Note 10 (also in PDF).
  11. Note 11 (also in PDF).
  12. Note 12 (also in PDF).
  13. Note 13 (also in PDF).


  1. Article on the relative worst order ratio (also in PDF). Older version of the paper, containing some of the missing proofs.
  2. Susanne Albers' lecture notes in BRICS lecture series, number LS-96-2.
  3. Michel Goemans has course notes on on-line algorithms on his home page.

IMADA HOME | SDU HOME | Previous page |
Last modified: June 25, 2003. - Joan Boyar <joan@imada.sdu.dk>