New and Improved Bounds for Markov Paging
For researchers in online algorithms and caching, this tightens the analysis of a classic polynomial-time algorithm for Markov paging.
The paper improves the competitive ratio of the dominating distribution algorithm for Markov paging from 4 to 2, and provides a lower bound of 1.5907 for the algorithm.
In the Markov paging model, one assumes that page requests are drawn from a Markov chain over the pages in memory, and the goal is to maintain a fast cache that suffers few page faults in expectation. While computing the optimal online algorithm $(\mathrm{OPT})$ for this problem naively takes time exponential in the size of the cache, the best-known polynomial-time approximation algorithm is the dominating distribution algorithm due to Lund, Phillips and Reingold (FOCS 1994), who showed that the algorithm is $4$-competitive against $\mathrm{OPT}$. We substantially improve their analysis and show that the dominating distribution algorithm is in fact $2$-competitive against $\mathrm{OPT}$. We also show a lower bound of $1.5907$-competitiveness for this algorithm -- to the best of our knowledge, no such lower bound was previously known.