Jelenlegi hely
Tanszékcsoporti szeminárium
Félév:
2014/15 II. félév
Helyszín:
Árpád tér 2. II. em. 220. sz.
Dátum:
2015-02-10
Időpont:
14:00-15:00
Előadó:
Jesper W. Mikkelsen (University of Southern Denmark)
Cím:
The Advice Complexity of Online Problems
Absztrakt:
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.