Megjelenik egy újabb cikk -- vééégre

A napokban kaptam értesítést arról, hogy megjelenik egy cikkünk. Hirtelen nem is tudtam, melyik cikkről szólnak. Aztán összeállt a kép. Ugyanis egy régen (még jóval a jelen projekt kezdete előtt fogadták el, és online nem sokkal a projekt kezdete előtt meg is jelent) elfogadott cikk papír változatáról szólt az értesítés. Volt már róla szó, hogy a matematikai témájú cikkek publikálási folyamata lassú, nem ritkán évekig eltarthat, elsősorban a bírálati folyamat nehézkessége miatt. Matematikában az eredmények helyességét ellenőrizni nehezebb, mint például egy pszichológiai témájú írás esetén. Itt azonban nem arról van szó: már elfogadott, online változatban megjelent cikk újságváltozatáról, évfolyammal, számmal, oldalszámmal. Rangosabb folyóiratoknál előfordul, hogy sok színvonalas írást küldenek be, egy számban korlátozott a benne megjelenő cikkek száma, így várólista alakul ki az elfogadott cikkekből, amelyek várják a sorukat, hogy bekerüljenek valamelyik számba. Ezért vezették be az online megjelentetést, hogy más kutatók addig is láthassák és hivatkozhassák (hiszen az impakt faktorba is csak a két éven belüli hivatkozások számítanak bele, a hivatkozás pedig az újság érdeke). Az online megjelenés is megjelenésnek számít, tehát nem változtatható, vagyis utólag nem íratható bele még támogatás szövege sem, hiába jelenik meg az újságváltozat egy adott projekt ideje alatt. Viszont az online megjelenés sok helyütt nem számít publikációnak, így kerül két szék között a földre egy kutató ilyen helyzetben, hiszen előfordulhat, hogy emiatt sehová sem tudja elszámolni a publikációját. Így jártam.

Visszatérve a hamarosan megjelenő cikkre: csak hogy nevet adjak a gyereknek, a

L. Epstein, Cs. Imreh, A. Levin, J. Nagy-György, Online File Caching with Rejection Penalties, ALGORITHMICA 71:279–306, 2015 

munkáról van szó. Ebben a publikációban a lapozási (paging) probléma kicsit más irányú általánosításáról van szó, mint a k-szerver probléma, de rokon vele valamilyen értelemben. A file caching problémában az input fájlokból álló kérések sorozata egy lassú memóriából. A fájlnak két attribútuma van, egy pozitív kinyerési költség és egy egész méret. Egy algoritmusnak egy k méretű cache-t kell fenntartani, úgy, hogy a cache-ben tárol fájlok teljes mérete sosem haladhatja meg k-t. Adott egy kérés egy fájlra, amely nincs jelen a cache-ben a kérés időpontjában, ekkor a fájlt a lassú memóriából a cache-be kell vinni, valószínűleg más fájlok elmozgatásával onnan. Ez a kért fájl kinyerési költségével jár. A lapozási problémán kívül (ahol minden költség és méret 1) a probléma jól ismert speciális esete a költség modell vagy más néven a súlyozott (weighted) lapozás, ahol minden méret 1, a hiba (fault) modell, ahol minden költség 1, és a bit modell, ahol minden fájl mérete és kinyerési költsége megegyezik. Ha figyelmen kívül hagyás (bypassing) megengedett, akkor a fájl hiány még mindig a fájl elérését eredményezi a lassú memóriából, de annak későbbi cache-be beszúrása optimális. Mi a fenti problémák online elutasításos változatát vizsgáltuk, amelyben minden egyes kéréshez büntetés is tartozik. Ekkor ha a cache-ben jelen nem lévő fájl kérését elutasítja az algoritmus, akkor a költségéhez a kérés büntetése járul hozzá. A célfüggvény az elutasított kérések büntetésének és az elfogadott kérések kinyerési költségének összege. Ez a probléma mind a caching, mind a caching with bypassing probléma általánosítása. Determinisztikus és véletlen algoritmusokat is kidolgoztunk. A véletlen algoritmus versenyképességi hányadosa O(log k), és ez konstans faktortól eltekintve optimális. A determinisztikus esetben ismert  k-versenyképes algoritmus a cachingre és (k+1)-versenyképes algoritmus a caching with bypassig problémára.Továbbá ezek a legjobb ismert versenyképességi hányadosok. Ezzel ellentétben megmutattunk egy 2k+1-es alsó korlátot az elutasításos változat determinisztikus algoritmusainak versenyképességi hányadosára, amely még a lapozásra is érvényes. Kidolgoztunk egy (2k+2)-versenyképes algoritmust az elutasításos caching problémára, valamint egy (2k+1)-versenyképes algoritmust, amely alkalmazható az elutasításos lapozásra, valamint a caching hiba és bit modelljeiben.