\input zb-basic
\input zb-ioport
\iteman{io-port 01771774}
\itemau{Bein, Wolfgang W.; Fleischer, Rudolf; Larmore, Lawrence L.}
\itemti{Limited bookmark randomized online algorithms for the paging problem.}
\itemso{Inf. Process. Lett. 76, No.4-6, 155-162 (2000).}
\itemab
Summary: An efficient randomized online algorithm for the paging problem for cache size 2 is given, which is $3/2$-competitive against an oblivious adversary. The algorithm keeps track of at most one page in slow memory at any time. A lower bound of $37/24\approx 1.5416$ is given for the competitiveness of any trackless online algorithm for the same problem, i.e., an algorithm that keeps track of no page outside the cache.
\itemrv{~}
\itemcc{}
\itemut{paging problem}
\itemli{doi:10.1016/S0020-0190(00)00140-X}
\end