Seminar SS2021
Current Topics in Online Algorithms
Contents
In online algorithms you have to make decisions while only seeing parts of the inputs. An example is the paging problem: If the cache is full, which page should I discard? There are different ways to judge how good an online algorithm is. We will look at new exciting developments of the last years.
Date and Time
The seminar will be held on a weekly basis. At the current time we expect the seminar to be held in online meetings. We expect you to actively participate during the presentations, e.g. asking many questions or activate the camera.The date of the kickoff-meeting will be announced before the start of the summer semester. The regular date and time will be announced after the topics are distributed.
Material
Dates and Topics
| Date | Topic | Student |
|---|---|---|
| 07.05.2021 | The start of Online Computation | Jannick Kremer |
| 07.05.2021 | The k-Server Problem | Hao Luo |
| 21.05.2021 | Randomization in Online Algorithms | - talk cancelled - |
| 21.05.2021 | Randomizing the Adversary | Jonathan Krapp |
| 04.06.2021 | Priority Algorithms | Ivan Ivanov |
| 04.06.2021 | Knapsack with Reservations | Roman Vuskov |
| 11.06.2021 | The Evolution of Advice Complexity | Gina Nottenkaemper |
| 11.06.2021 | The Tape Model for Advice Complexity | Kai Ortmanns |
| 18.06.2021 | The k-Taxi Problem | Torben Zimmer, Jan Ackermann |
| 25.06.2021 | Online Computation with Untrusted Advice | Maximilian Hermans |
| 25.06.2021 | The Online Knapsack Problem: Advice and Randomization | Moritz Koehl |
| 02.07.2021 | Machine learned Advice | Jakob Miesner, Niels Mittelstaedt |
| 09.07.2021 | Deleting Nodes and Edges with Advice while Delaying Decisions | Mats Bierwirth, Ben Sturgis |
| 16.07.2021 | String Guessing | Berke Kisin |
| 16.07.2021 | Problems and Critique Regarding Online Computation | Sven Kuffer |
| 23.07.2021 | Edge Weighted Online Bipartite Matching | Adrian Gallus, Xaver Fink |