onl Online Algorithms (Summer 2014)
max planck institut
mpii logo Minerva of the Max Planck Society


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.
Date Topic Exercises
Apr 15 Introduction to Online Algorithms. The ski rental
problem, the cow path problem and paging.
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:40 reserved
10:20 reserved
11:00 reserved
Lecture Notes:
Further Literature:

More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)