This is an archived website. The group moved to RWTH Aachen University.

Aktuelle Themen in Algorithmen für große Datenmengen 1+2:
Optimization and Uncertainty (Summer 2021)


Topical


Organization


Material

Lecture Notes

Current update: 8 July 2021 (restricted access).


Videos

Videos are available here. (restricted access)

Unlock Features: Click "play" on the video and then "pop-out" (lower right). This opens a separate window with the same video, in which you can see annotations, scroll in the timeline, and speed up/down the video.


Exercises

Each assignment is published on Tuesday and is due the following Tuesday at 10:00h. Your solutions have to be submitted as one PDF-file via e-mail to Lisa Wilhelmi. Exercise sessions are scheduled on Friday 12:15 - 13:45h via Zoom.


Exercise Sheets


Part 1:
Part 2:

Topic

Suppose you go on a sequence of n dates, after each of which you have to decide if you want to start a relationship or see more people - when is the best time to stop dating to get the best partner? Optimization problems of this type arise frequently in modern computer systems. Often large data sets can be used to infer probabilistic information about the expected benefit of the potential decisions. The course gives an introduction to algorithmic techniques for solving optimization problems with uncertainty. We will start with classic stopping problems as the one sketeched above (i.e., secretary and prophet-inequality problems) and advance to more general online optimization problems in which the input is partly stochastic and partly adversarial. Futher topics of interest are recent developments in online learning, Markov decision processes, testing and probing problems, as well as applications of these techniques in distributed systems and markets.


Literature