Először is mik azok az online algoritmusok? Nagyon pongyolán fogalmazva olyan algoritmusok, amelyek nem egyben kapják meg az inputot, hanem részletekben, és a kapott inputrészlettel kapcsolatban azonnali és visszavonhatatlan döntést kell hozni. Általában optimalizálási (minimalizálási vagy maximalizálási) problémáknak vizsgálják online változatát. Általában azt vizsgálják, az online változat célfüggvény értéke mennyivel rosszabb az offline (azaz ahol az input egyben jön) változaténál. Erre vezetik be a versenyképességi hányadost (competitive ratio).
Mire jó ez? A valósághoz közelebbi modellt szerettek volna létrehozni, hiszen a valóságban sem tudjuk sokszor a jövőt, mégis döntenünk kell: pl. egy gyárban gépekre kell kiosztani a munkákat, valamilyen szempont szerint hatékonyan, egy adott munka kiosztásakor (amivel nem várhatunk) nem tudhatjuk, hogy ha valahogy kiosztjuk, nem kapunk-e olyan munkát a jövőben, ami miatt jobb lett volna máshogy kiosztani.
Hogyan lehet ezt kutatni? Nyitott kérdések mindig vannak. Az online algoritmusok területén ez hatványozottan érvényes. Mindig találhatunk olyan optimalizálási problémát, amely online változata még megoldatlan. Ha találtunk egy ilyet, két irányból támadjuk meg:
1. megpróbálunk hatékony online algoritmust konstruálni (ez a könnyebb) és bizonyítani, hogy nem sokkal rosszabb az outputja, mint az optimális (ez a nehezebb), ez adja pl. minimalizálási probléma esetén a felső korlátot,
2. megpróbálunk minden online algoritmushoz konstruálni olyan inputot, amelyre az online algoritmus valamennyivel rosszabb eredményt ad mint az optimális (ezt egy tanárom "kisördög módszer"-nek nevezte), ez adja pl. minimalizálási probléma esetén az alsó korlátot.
Kutatásaimban most leginkább az online algoritmusok elutasításos változatára fogok fókuszálni, amiben az alapprobléma azzal van megspékelve, hogy minden inputrészlethez egy büntetés érték tartozik, az online algoritmusnak lehetősége van elutasítani az adott inputrészletet (mintha nem is jött volna), de ekkor a büntetést ki kell fizetnie. Ennek is van valós alapja: egy megrendelést vissza lehet utasítani, ekkor büntetésként foghatjuk fel a meg nem kapott profitot. Következő bejegyzésben konkrét példákat is láthatunk majd.
--ngyj
