Seminar SS2025

Online Algorithms

Contents

In online algorithms however you have to make decisions while only seeing parts of the inputs, which arguably is a more natural setting. 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. In this Seminar, we will first focus on the conceptual basics of the online setting and the classical problems in it. Therefore potential topics will include what competitive analysis is; what impact randomization, advice or predictions could have, how upper and lower bounds work here, etc. Afterwards, we will have a look into recent trends and publications in this area. Note that participating in this seminar requires a registration on Supra from 6th to 13th January 2025!

Date and Time

We will meet at the beginning of the lecture period for a kickoff meeting and a distribution of the topics, the talks will likely be held en block in the week from 7th to 11th of July. The date of the kickoff-meeting will be announced before the start of the summer semester.