Teaching

Optimizing with Uncertainty: An Introduction to Online Algorithms and Algorithmic Game Theory

Course in Winter 2017/18


Traditional optimization theory assumes complete knowledge of information. However, in reality, input might be uncertain - they might be incomplete, revealed over time or might involve choices made by selfish players. In this course, we shall deal with solving optimization problems under such uncertainties.

In the first part of the course, we shall develop the notion of online computation - an area which deals with developing algorithms that make decisions on the basis of input that is built over time. We shall introduce formal models of measuring the efficiency of such algorithms and develop algorithms for various flavors of online optimization problems. These problems find applications in areas such as planning, logistics, communication or machine learning.

In the second part, we learn to handle situations where we are not all-powerful, but instead have to deal with other decision makers as well. We learn to design mechanisms that take into account the actions of these strategic players and how to analyze the performance of these mechanisms. We encounter this type of problems in transportation and data networks, (online) auctions, and assigning students to schools.

Lecturers:
Dr. Ruben Hoeksma
Dr. Syamantak Das (Email)
Time & Room:

Tue : 14:00-16:00 ; MZH 1450
Thu : 16:00-18:00 ; MZH 1100
Begin:

TBA
Literature: The course is based on parts of the literature below and recent research articles that will be added later.
Date Topic Notes Exercises
17.10.2017 Introduction, Ski-Rental Lecture 1 Exercise 1
19.10.2017 Deterministic paging algorithms Lecture 2 -
24.10.2017 List Update Problem - -
26.10.2017 Exercise session - -
31.10.2017 No lecture (Day of German Unity) - -
02.11.2017 Makespan minimization on identical parallel machines - -
07.11.2017 Makespan minimization under restricted assignments Lecture 4,5 Exercise 2
09.11.2017 Exercises - -
14.11.2017 Randomized Paging Algorithm Basic probability Notes by Luca Trevisan Exercise 3