Bi-Weekly Talk: Introduction to Online Algorithms with Advice

Wednesday, 02.05.2018, 10:15am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10


Speaker: Janosh Fuchs


Online algorithms serve as a model for computational problems where the input is not known at the beginning of the computation, but arrives piece-wise over time. In the classical model, an online algorithm does not know anything about the future parts of the input. In some scenarios, this assumption might be too pessimistic.

For a more fine-grained analysis of how much information about the unknown instance is really needed, we look at an extension of the classical online setting where the algorithm has access to some information in the form of a bit string, provided by a helpful oracle that knows the input.

The number of bits that the algorithm reads until it finishes its computation is then called its advice complexity.

The talk gives a brief overview of the topic and presents examples to introduce basic techniques.