First meeting: 18th April, 2pm, T9/051 Seminarraum

tentative plan (to be updated as we go)

Contents

Online algorithms are used in scenarios where the input is revealed gradually, for instance in learning tasks, or when there is interaction between agents, or between an agent and its environment. The primary concern is dealing with uncertainty and to find good solutions even with partial information; in this setting computational efficiency often takes a secondary role.

The field of online algorithms is one of the most active areas of algorithmic research with a rich set of established techniques developed during the past decades, as well as recent exciting breakthroughs and open questions.

The seminar is aimed at students interested in algorithms and theoretical computer science.  Requirement: ALP3/HA or similar algorithmic background, mathematical maturity.

We can cover some subset of the following topics: caching, paging, load balancing, routing, navigation, data structuring, k-server, scheduling, ski rental, online learning, packing and covering, coloring, primal-dual methods, online algorithms with advice, and others.

Presentations will be in English, topics can be based on articles or selected material from the books:

• Borodin and El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998
• Buchbinder and Naor: The Design of Competitive Online Algorithms via a Primal-Dual Approach, Foundations and Trends in TCS, 2009
• Fiat and Woeginger: Online Algorithms, The State of the Art, Springer, 1998

First meeting: 18th April, 2pm, T9/051 Seminarraum