DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.123

New and Improved Bounds for Markov Paging

Authors: Chirag Pabbaraju and Ali Vakilian

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

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.

Cite as

Chirag Pabbaraju and Ali Vakilian. New and Improved Bounds for Markov Paging. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 123:1-123:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pabbaraju_et_al:LIPIcs.ICALP.2025.123,
  author =	{Pabbaraju, Chirag and Vakilian, Ali},
  title =	{{New and Improved Bounds for Markov Paging}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{123:1--123:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.123},
  URN =		{urn:nbn:de:0030-drops-235005},
  doi =		{10.4230/LIPIcs.ICALP.2025.123},
  annote =	{Keywords: Beyond Worst-case Analyis, Online Paging, Markov Paging}
}

Search Results

Documents authored by Pabbaraju, Chirag

New and Improved Bounds for Markov Paging

Abstract

Cite as

Thanks for your feedback!

Could not send message