2026-07-24T18:10:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23500 2025-10-02T12:56:58Z ddc:004 open_access

New and Improved Bounds for Markov Paging Pabbaraju, Chirag Vakilian, Ali Beyond Worst-case Analyis Online Paging Markov Paging 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chirag Pabbaraju and Ali Vakilian 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.123 urn:nbn:de:0030-drops-235005 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.123 eng https://creativecommons.org/licenses/by/4.0/legalcode