Nagy-György Judit: Útgráfok online élszínezése |
||||
|
||||
|
||||
Absztrakt. Optimalizációs problémák online változatának nevezzük azt a modellt, amikor az inputot nem egyben kapja meg az algoritmus, hanem részleteiben, a megkapott részletről azonnal döntenie kell, ezt utólag nem módosítatja. A célfüggvényértéket az optimális célfüggvényértékhez viszonyítva vizsgálják, véletlen algoritmus esetén várható értékben. Mindez tekinthető játéknak is, amikor az egyik játékos maga az algoritmus, az ellenfele pedig az inputot adja. Az elemzésben két hasznos technika, a töltésszétosztás és Yao minimax elvének alkalmazását szeretném bemutatni konkrét példán (utak élszínezése) keresztül Favrholdt és Mikkelsen cikke alapján: https://arxiv.org/pdf/1405.3817v2.pdf |
||||
Hely : Szeged, Aradi vértanúk tere 1., Riesz terem. |
JEvents v3.1.8 Stable Copyright © 2006-2013