2025/02/08 by Pabbaraju, Chirag, Vakilian, Ali
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.05511
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 (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 OPT. We substantially improve their analysis and show that the dominating distribution algorithm is in fact 2-competitive against 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.