Online Algorithms

Abstract

The course gives an introduction to the competitive analysis ofonline algorithms. Online algorithms must decidehow to act on incoming pieces of information without anyknowledge of future inputs. Online problems occur in applications suchas paging, scheduling, load balancing, and routing.

Objective

The course teaches various techniques for the design and analysis of online algorithms.

Content

The course will give an introduction to the competitive analysis of online algorithms. Online algorithms must decide how to act on incoming pieces of information without any knowledge of future inputs. Online problems occur, for example, in caching and paging (which cache block should be evicted when the cache is full?), in scheduling and load balancing (which job should be executed next and on which machine?), in call admission control and routing (should a newly requested connection be admitted into the network and along which path should it be routed?), and in robot navigation (which strategy should a robot use to explore an unknown environment?). In the framework of competitive analysis, the solution computed by the algorithm is compared with the best possible solution that could have been computed with unlimited computational power and complete advance knowledge of the whole input sequence. In the course, we will discuss various techniques for the design and analysis of online algorithms and apply them to problems arising in applications such as paging, real-time scheduling, load balancing, and routing and call admission control.

Resources