FS 2025 — Dr. H.-J. Böckenhauer, 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.

In this seminar, we want to review known results on the k-server problem, which is one of the most prominent online problems. Here, the requests are located at specific positions in a given metric space. To serve a request one of k servers (agents) has to be moved to the requested point. The objective is to minimize the total distance traveled by all servers.

In the first part of the seminar, we wil look at algorithms for the k-server problem and some of its variants and generalizations in this classical online setting. In the second part, we will consider several semi-online setting in which the algorithm is equipped with some extra information or capabilities. As an example, 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.

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

Organization

• The kick-off meeting will take place on Thursday, February 20, 2025, from 4:15pm to 6pm in room CAB H 52. In this meeting, we will distribute the topics among the participants.
• The presentations will be held as a block course on June 10-12, 2025.
• 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.