First meeting: 18th April, 2pm, T9/051 Seminarraum
tentative plan (to be updated as we go)
| Valentin Pickel |
Metrical Task Systems and the Work Function Algorithm |
2 May |
| Kalapuram
Chandramouli Reddy
|
Load Balancing | 9 May |
|
Antonia Liebenberg Sebastian Bentert |
Robot Navigation [slides] Game theory [slides] |
16 May |
|
Dilay Hamaykaya Arman Durmus |
Online Packing | 6 June |
|
Fatih Ibrahimbas Tolga Yurtseven |
Online Matching [slides] | 13 June |
|
Karim Ismail |
Ski Rental |
20 June |
| Jung Nguyen + Rui Xu |
Convex optimization and learning [notes] |
27 June |
|
David Knaack Yagmur Simsek |
Online (interval) Coloring List update |
4 July |
| Nils Liebreich + Ming Lu | k-Server [partial notes] | 7 July |
Contents
Online algorithms are used in scenarios where the input is revealed gradually, for instance in learning tasks, or when there is interaction between agents, or between an agent and its environment. The primary concern is dealing with uncertainty and to find good solutions even with partial information; in this setting computational efficiency often takes a secondary role.
The field of online algorithms is one of the most active areas of algorithmic research with a rich set of established techniques developed during the past decades, as well as recent exciting breakthroughs and open questions.
The seminar is aimed at students interested in algorithms and theoretical computer science. Requirement: ALP3/HA or similar algorithmic background, mathematical maturity.
We can cover some subset of the following topics: caching, paging, load balancing, routing, navigation, data structuring, k-server, scheduling, ski rental, online learning, packing and covering, coloring, primal-dual methods, online algorithms with advice, and others.
Presentations will be in English, topics can be based on articles or selected material from the books:
- Borodin and El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998
- Buchbinder and Naor: The Design of Competitive Online Algorithms via a Primal-Dual Approach, Foundations and Trends in TCS, 2009
- Fiat and Woeginger: Online Algorithms, The State of the Art, Springer, 1998
First meeting: 18th April, 2pm, T9/051 Seminarraum