Competitive Online Algorithms

Susanne Albers

September 1996

Abstract:

These lecture notes are from the mini-course ``Competitive Online Algorithms'' taught at Aarhus University, August 27-29, 1996.

The mini-course consisted of three lectures. In the first lecture we gave basic definitions and presented important techniques that are used in the study on online algorithms. The paging problem was always the running example to explain and illustrate the material. We also discussed the k-server problem, which is a very well-studied generalization of the paging problem.

The second lecture was concerned with self-organizing data structures, in particular self-organizing linear lists. We presented results on deterministic and randomized online algorithms. Furthermore, we showed that linear lists can be used to build very effective data compression schemes and reported on theoretical as well as experimental results.

In the third lecture we discussed three application areas in which interesting online problems arise. The areas were (1) distributed data management, (2) scheduling and load balancing, and (3) robot navigation and exploration. In each of these fields we gave some important results.

Contents

1

Online algorithms and competitive analysis

1.1

Basic definitions

1.2

Results on deterministic paging algorithms

2

Randomization in online algorithms

2.1

General concepts

2.2

Randomized paging algorithms against oblivious adversaries

3

Proof techniques

3.1

Potential functions

3.2

Yao's minimax principle

4

The k-server problem

5

The list update problem

5.1

Deterministic online algorithms

5.2

Randomized online algorithms

5.3

Average case analyses of list update algorithms

6

Data compression based on linear lists

6.1

Theoretical results

6.2

Experimental results

6.3

The compression algorithm by Burrows and Wheeler

7

Distributed data management

7.1

Formal definition of migration and replication problems

7.2

Page migration

7.3

Page replication

7.4

Page allocation

8

Scheduling and load balancing

8.1

Scheduling

8.2

Load balancing

9

Robot navigation and exploration

Available as PostScript, DVI, Slides: 1 page on each sheet of paper ( PDF, PostScript) and 2 pages on each sheet of paper (both PostScript, approx. 4 Mb compressed to 0.4 Mb).