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.