Online-Algorithms for k-server and related Problems

Abstract

In the online k-server problem, some agents (servers) have to be moved around in a metric space such as to serve some requests at initially unknown positions. Taking this prominent example, we want to survey methods for analyzing algorithms both in the classical online setting and in several semi-online settings

Objective

To systematically acquire an overview of methods for designing and analyzing online algorithms using the k-server problem and its variants as an example. To get an overview of modern approaches to semi-online problems, where the online algorithm has some additional information available, e.g., some machine-learned predictions about future requests.

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.

Resources