A következő kombinatorika szeminárium ideje
<P><CENTER>
               február 13. (péntek), 10:00
</CENTER>
helye
<P><CENTER>
            Riesz terem (Bolyai épület, I. emelet).
</CENTER>
Ez a terem az Aradi Vértanúk teri lépcsőházból nyilik. Az előadás:

<P>


<P><CENTER>
Jesper W. Mikkelsen (University of Southern Denmark):
<B>The Advice Complexity of Online Problems</B>
</CENTER>



<P>
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.

<P>
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).

<P>
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.

<P>
Az előadásra minden érdeklődőt szeretettel várunk,

<P>
Péter

<P>
<IMG SRC="infoblokk_kedv_final_magyar.jpg" height="61">
<IMG SRC="szte_cimer.jpg" height="61">
<IMG SRC="Szechenyi2020.jpg" height="61">
<P>
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"