BRICS · Contents · Programme · Lecture Notes

**A BRICS Mini-Course**

**August 27-29, 1996**

**Lectures by
Susanne Albers
**

**
**

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.

- Paging.
- Self-organizing data structures; we will also show how algorithms in this field can be used to construct data compression schemes.
- Scheduling.
- Navigation and exploration.
- 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