A következő kombinatorika szeminárium ideje
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).
The talk will be accessible to everyone, even if you have never heard of online algorithms before. There will be a shorter talk with the same title (but without mathematical details) at the seminar of the Institute of Informatics on Tuesday 10th.
Az előadásra minden érdeklődőt szeretettel várunk,
Péter
Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073 projekt, "Telemedicina fókuszú kutatások Orvosi, Matematikai és Informatikai tudományterületeken"