Modulcode:	infOnAlg-01a
Englische Bezeichnung:	Online Algorithms
Modulverantwortliche(r):	Dr. Sebastian Berndt
Turnus:	jedes Jahr im WS (WS18/19)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MSc WInf (15))
Lehrsprache:	Englisch
Voraussetzungen:	Inf-ADS

Kurzfassung:

In this course we will look at the topic of online algorithms. These are algorithms that receive their input over time, whereas classical offline algorithms receive their input completely at once. Hence, online algorithms need to deal with uncertain inputs. We present several online algorithms from different areas such as data management, scheduling, and machine learning. In addition, we will analyze the algorithms' behavior in terms of running time, competitiveness, etc. We will also take a look at lower bounds regarding these parameters using different tools.

Lernziele:

We expect that participants of this course will be able do design and analyze online algorithms. They will be able to understand the feasibilities and limitations of such algorithms and will be able to judge the need for handling uncertain inputs in different areas.

Lehrinhalte:

The main topics the course will cover are: paging algorithms, multiplicative weights algorithm, use of potential functions, robust packing and scheduling algorithms, dual fitting approach, metric task systems, load balancing, lower bounds, online matching, secretary problem. We will also take a look at current work related to these problems.

Weitere Voraussetzungen:

Algorithms and Data Structures

Prüfungsleistung:

There will be an oral exam after the course. In order to participate in this exam, 75% of the exercises need to be worked on meaningful. Additionaly, details of one lecture should be scribed by taking notes.

Lehr- und Lernmethoden:

lecture with beamer and black board presentation; exercises

Verwendbarkeit:

Literatur:

• Allan Borodin and Ran El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press, 0-521-56392-5, 2008.
• Niv Buchbinder and Joseph Naor, The Design of Competitive Online Algorithms via a Primal-Dual Approach. Foundations and Trends in Theoretical Computer Science Vol. 3, Nos. 2-3, 93-263, DOI: 10.1561/0400000024, 2007.
• Susanne Albers, Lecture notes on competitive online algorithms. BRICS Lecture Series LS-96-2, Århus University, Denmark, 1996.
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms. Cambridge University Press, 0-521-47465-5, 1995.
• Amos Fiat and Gerhard Woeginger, Online Algorithms: The State of the Art. Springer, 978-3-540-68311-7, 1998.
• Thomas Kesselheim, Ausgewählte Kapitel der Algorithmik: Algorithmen und Unsicherheit. Lecture Notes, TU Dortmund, 2017.
• Kamesh Munagala, Optimization and Decision-making under Uncertainty. Lecture Notes, Duke University, 2016.

Verweise:

Kommentar: