FS 2024 — Dr. H.-J. Böckenhauer, Dr. F. Frei, Prof. Dr. D. Komm

Seminar: Algorithms with Predictions

Content

In the classical model of online algorithms, one assumes that the input is revealed piecewise in the form of requests over time and an algorithm has to respond with a part of the output to each request. While there are many situations in which this model is more realistic than the classical model of computation where the whole input is known in advance, not knowing anything about future requests is a quite pessimistic assumption.

Recently, several approaches have been introduced to incorporate some kind of predictions about future requests into the model. These predictions can, e.g., be based on some statistical knowledge about typical instances or can be generated by some machine-learning approaches.

In this seminar, after some brief introduction to online algorithms, we want to explore the impact of different kinds of predictions on the solution quality of online algorithms.

Each participant will study one aspect of this topic, following a specific scientific publication, and will give a presentation about this topic.

Organization

• The kick-off meeting will take place on Thursday, February 22, 2024, from 4:15pm to 6pm in room CAB H 53. In this meeting, we will distribute the topics among the participants and decide on the exact date for the presentations.
• The presentations will be held as a block course in the first week of June 2024. More details will be announced at the kick-off meeting.
• The list of topics together with the corresponding literature will be published on Moodle.
• All further information on the seminar will be also published on Moodle.

Contact: Dr. Hans-Joachim Böckenhauer, ; last change: ; Disclaimer.