Jelenlegi hely

Tanszékcsoporti szeminárium

2014/15 II. félév
Árpád tér 2. II. em. 220. sz.
Jesper W. Mikkelsen (University of Southern Denmark)
The Advice Complexity of Online Problems
An online problem is an optimization problem in which the input arrives
sequentially over time, usually as a number of requests. Traditionally, an
online algorithm must serve each request irrevocably without any knowledge
of future requests. Sometimes, the assumption that nothing at all is known
about the future is unrealistic and leads to overly pessimistic results.
Therefore, it is interesting to consider the situation where the online
algorithm has partial (but incomplete) knowledge of the future. In this
talk, we will survey the recent idea of advice complexity. The advice
complexity of an online problem is a measure of how many bits of advice an
online algorithm needs in order to achieve a certain quality of solution.

In the talk, we will illustrate the main ideas and challenges of advice
complexity by considering some concrete problems:

   - Online bin packing. For this problem, it turns out that even a small
amount of advice is very helpful.
   - Online graph problems like minimum edge coloring and minimum vertex
cover. For these problems, it turns out that a lot of advice is needed
to obtain a significant improvement compared to algorithms having no
advice at all.

The talk will be easily accessible and based on (selected parts of) the
following papers.

[1] Joan Boyar, Lene M. Favrholdt, Christian Kudahl and Jesper W.
Mikkelsen: Advice Complexity for a Class of Online Problems. STACS 2015.
[2] Joan Boyar, Shahin Kamali, Kim S. Larsen, Alejandro López-Ortiz:
Online Bin Packing with Advice. STACS 2014.
[3] Jesper W. Mikkelsen: Optimal Online Edge Coloring of Planar Graphs
with Advice. CIAC 2015.