Computational optimization problems that arise in real-life scenarios often involve uncertainty about the input data. One such common scenario is the online setting, where the input sequence arrives piecewise over time, and an online algorithm needs to incrementally and irrevocably update its solution at each step.

The most common performance measure of online algorithms is their competitive ratio, defined as the worst-case ratio between the algorithm’s solution and the optimal solution. Since its introduction in the mid-1980s, the competitive ratio approach has been used to analyze optimization problems in a wide range of areas, including data structures (list up-date, splay trees), computer systems (paging, caching), networking (packet scheduling), distributed systems (file migration), and others. Several abstract models for online problems were developed, including the k-server problem, metrical task systems and LP-based models, with the goal of developing general techniques for the design and analysis of competitive algorithms. Competitive analysis has been adopted by some researchers in applied fields, where it is sometimes used in conjunction with experimental analyses. In another direction of research, refined models of competitive analysis have been proposed, to address its sometimes overly pessimistic bounds or to customize it towards capturing more subtle aspects of performance.

While the field of competitive analysis has expanded considerably over the last four decades, there has been relatively little progress on developing generally applicable techniques for algorithm design and analysis, and some core problems in this area still remain open. This Dagstuhl Seminar is intended to cover latest developments in the area of online algorithms and to assess the state of the art in this field, 40 years after inception. The seminar’s program will be a mixture of technical talks, expository surveys, and open problem sessions. Of particular interest will be presentations that examine fundamental aspects of competitive analysis, including general models and general techniques, and report on progress on resolving the outstanding open problems in this area.

Creative Commons BY 4.0

Susanne Albers, Marek Chrobak, Elias Koutsoupias, and Adi Rosén