Jesper W. Mikkelsen (University of Southern Denmark): The advice complexity of online problems |
|
|
|
|
Friday, 13. February 2015, 10:00 - 12:00
|
|
Abstract. An online problem is a combinatorial optimization problem in which the input arrives sequentially over time. Traditionally, an online algorithm must solve each part of the problem without any knowledge of future parts of the input. In this talk, we will consider the recently introduced notion of advice complexity. The basic idea of advice complexity is to provide the algorithm with partial knowledge of the future. The main question is how many bits of advice an online algorithm needs in order to achieve a certain performance guarantee.
We will illustrate the main ideas of advice complexity by applying it to online bin packing and to online graph problems like vertex cover and independent set. As one of the main results, we will prove a strong relationship between advice complexity and combinatorial design theory (covering designs and covering codes). |
|
Location : Riesz terem |
Back
JEvents v3.1.8 Stable
Copyright © 2006-2013
Export Event