BRICS · Contents · Programme · Lecture Notes

Competitive Online Algorithms

A BRICS Mini-Course
August 27-29, 1996

Lectures by
Susanne Albers
Max-Planck-Institut für Informatik, Saarbrücken, Germany


Course Contents

Online algorithms represent a relatively new area of research that has developed in the past ten years. An online algorithm receives the input incrementally, one piece at a time, and must process each input portion without knowing future portions. An online algorithm A is called c-competitive if, for every input sequence, the cost incurred by A is at most c times the optimal offline cost for that sequence. In this mini-course we will present the most important concepts and techniques used in the study of deterministic and randomized online algorithms.

Research on online algorithms in generally motivated by real online problems that arise in practice. In the mini-course we will discuss in detail algorithms for the following applications.

  1. Paging.
  2. Self-organizing data structures; we will also show how algorithms in this field can be used to construct data compression schemes.
  3. Scheduling.
  4. Navigation and exploration.
  5. Distributed computing

    Programme

    Tuesday August 27, 1996, 10:15-12:00 in Auditorium D3

    Wednesday August 28, 1996, 10:15-12:00 in Auditorium D3

    Thursday August 29, 1996, 10:15-12:00 in Auditorium D3

    Lecture Notes

    BRICS-LS-96-2