Teaching

Online Algorithms (Summer 2014)

Time:

Tuesday, 10:15 a.m. to 11:45 a.m.

First meeting:

Tuesday, 15.04.

Lecturers:

Antonios Antoniadis and Martin Hoefer

Tutorials:

every second Thursday, 10:15 a.m. to 11:45 a.m.

Room:

024 on the ground floor of the MPI building (E1.4).

Prerequisites:

Basics in algorithm design, probability theory and calculus.

Description:

In classical algorithm theory, it is assumed that the whole input to the problem is known in advance. However, in many practical scenarios the input arrives piecewise over time, which can force an algorithm into making suboptimal decisions. In this lecture, we will develop algorithms that attempt to overcome this obstacle of not knowing the future.

The problems that will be studied in the lecture include:

Paging
The k-Server problem
Online Matching
Online Scheduling
Online Linear Programming
Online Secretary problems
Exploration

Credits:

This is a 5-credit-points class. There will be one lecture per week and one tutorial session every second week.

Exercises:

We will hand out exercise sheets roughly every two weeks. An average score of at least 50% is a prerequisite for participation in the exam.

Schedule:

Date	Topic	Exercises
Apr 15	Introduction to Online Algorithms. The ski rental problem, the cow path problem and paging.	1
Apr 22	Paging.
Apr 29	Paging. k-server problem.
May 6	k-server problem. Introduction to potential functions. List update problem.	2
May 8	Discussion of exercise sheet 1
May 13	Potential functions continued: List update problem & online scheduling.
May 20	Online scheduling.	3
May 22	Discussion of exercise sheet 2
May 27	Online scheduling. Online exploration.
Jun 3	Online Linear Programming [pdf, 14.06.14]	4
Jun 5	Discussion of exercise sheet 3. Room change: SR 015 E1 3!
Jun 10	Online Linear Programming
Jun 17	Online Linear Programming
Jun 24	Secretary Problems [pdf, 26.07.14]	5
Jun 26	Discussion of exercise sheet 4
Jul 1	Secretary Matching
Jul 3	Discussion of exercise sheet 5
Jul 8	Online Matching	6
Jul 17	Prophet Inequalities
Jul 22	Secretary Independent Set [pdf, 26.07.14]
Jul 24	Discussion of exercise sheet 6

Exam schedule:

Time	04.08.	06.10.
9:00
9:40		reserved
10:20		reserved
11:00		reserved
11:40
14:00
14:40
15:20
16:00
16:40

Lecture Notes:

Further Literature:

More Courses of the Algorithms and Complexity Group