Seminar SS2021

Current Topics in Online Algorithms

Online banner

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