Online Algorithms

Abstract

We look into algorithmic approaches for dealing with online problems and related models of incomplete information. An online problem models a situation where an algorithm has to react to a sequence of requests without revoking decisions once taken. Besides classical online resource allocation problems, we also consider the analysis of greedy algorithms and the exploration of unknown terrains.

Objective

To systematically acquire an overview of the methods for analyzing the complexity of online algorithms. To get deeper knowledge of the approaches of competitive analysis and advice complexity. To learn how to extend the applicability of these tools to analyze exploration problems and the analysis of greedy algorithms.

Content

In this seminar, we will discuss algorithmic approaches for solving online problems and analyzing their hardness. In the kick-off meeting, we will give a brief overview of these approaches, including competitive analysis and advice complexity. We will also discuss other models of incomplete information related to online problems. Then, each participant will study one aspect of this topic, following a specific scientific publication, and will give a presentation about this topic. The topics will include the competitive analysis of both deterministic and randomized algorithms for several classical online problems, the recent method of advice complexity as a means for determining the hardness of online problems, as well as several related computational problems like exploring an unknown environment by some agent with limited, local perception abilities or the analysis of the power of greedy strategies. We will focus on techniques for which certain worst-case performance guarantees can be proven.

Resources