Ennyi felvezetés után itt az ideje olyan nyitott kérdéseket nézni, amelyeket érdemes lehet vizsgálni (nem garantálom, hogy az, hiszen a kérdések nyitottak, vizsgálatuk nem vezet feltétlen eget verően érdekes eredményekre).
Ezen a területen olyan nyitott problémákat szokás vizsgálni, amelyek nem elutasításos változata már eléggé feltárt terület, különben általában az elutasítás nélküli változatnak esnek neki (kivétel lehet olyan terület, amely elutasításos változata gyakorlatilag jobban motivált, de ilyenbe még nem botlottam). A felsorolt problémák sem időrendet, sem másmilyen logikai sorrendet nem fognak követni, úgy írom le, ahogy eszembe jutnak. Nem lesz teljes a lista, azon problémaköröket érinti, amelyek foglalkoztatnak.
1. gráfszínezés. Az online gráfszínezésnek kiterjedt irodalma van, a régebbi eredményeket a
H. A. Kierstead, Coloring Graphs On-line, Online algorithms: The State of the Art (A. Fiat, and G. J. Woeginger (eds.)), Vol. 1442 of Lecture Notes in Computer Science, Springer-Verlag Berlin, Heidelberg, 281–305, 1998. összefoglaló cikkben olvashatjuk.
Az eredeti online modellben a gráf csúcsai érkeznek egyesével, az eddig érkezett csúcsok által feszített részgráfot látjuk, így kell az új csúcsot színezni. A költség a felhasznált színek száma. Az elutasításos változatban minden csúcshoz tartozik egy büntetés is, amit akkor fizetünk, ha azt a csúcsot nem színezzük. Ez a büntetés hozzáadódik a költséghez. Már a büntetés nélküli változatra is igaz, hogy nincs konstans versenyképes algoritmus, így speciális gráfosztályokat szoktak vizsgálni. Tehát az elutasításos esetben sem lesz (nyilvánvalóan az elutasítás nélküli alsó korlátok az elutasításos esetre is érvényesek), és érdemes megvizsgálni ugyanazokat gráfosztályokat (esetleg újakat).
2. lista színezés. Ez a probléma kilóg a sorból. Valójában már az is kérdéses, hogy hogyan definiálható az elutasításos változat, vagy van-e értelme, ráadásul az eredeti problémakörben is sok nyitott kérdés van, tehát a kutatást az elutasítás nélküli változattal érdemes kezdeni, ami szerintem szintén érdekes. Az online gráfszínezéssel összevetve ez egy furcsa modell. Itt előre ismerjük a gráfot, és nem a csúcsokat, hanem a színeket kapjuk, minden lépésben azon csúcsok felsorolásával, amelyek azzal a színnel színezhetők, és meg kell mondani, mely csúcsok kapják majd ténylegesen azt a színt (helyes színezést kell itt is kapjunk). A modellt a színező és ellenfele közti játékkal szokták megfogalmazni: a színező ellenfele adja az inputot, a színező választja ki az adott színűre színezendő csúcsokat. A játékhoz adott egy csúcsokon értelmezett f függvény, amely természetes számokat rendel a csúcsokhoz. A színező veszít, ha van olyan v csúcs, amelyet már f(v)-szer kapott, de nem színezett ki. A gráf online f-choosable, ha van a színezőnek nyerő stratégiája. Az online choise number a legkisebb k, amelyre a gráf k-choosable, azaz f-choosable az f azonosan k konstans függvénnyel. Kevés eredmény van a területen, ezek is csak azokat a gráfokat szeretnék karakterizálni (eddig viszonylag nem sok sikerrel), amelyek online choise number-ük megegyezik a kromatikus számukkal.
Mi lenne itt az elutasításos változat (már ha eljutunk annak vizsgálatáig)?
folyt. köv.
Nincsenek megjegyzések:
Megjegyzés küldése