New and Improved Bounds for Markov Paging
Chirag Pabbaraju, Ali Vakilian · 2025
Read New and Improved Bounds for Markov Paging by Chirag Pabbaraju, Ali Vakilian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05511.txt.
Description
Chirag Pabbaraju and Ali Vakilian wrote this 2025 theory paper on paging, the task of keeping the most useful pages in a small fast cache. In the Markov version of the task, page requests follow a chance pattern with memory, and the goal is few cache misses on average. A classic method from 1994 was long known to cost at most four times the best possible offline cost.
The authors sharpen the proof for that classic method and show it is in fact at most twice the best cost. They also prove a lower bound: no run of the method can promise better than about 1.59 times the best cost in the worst case. No such lower bound was known before, so the work closes much of the gap on this method.
Catalog record
| CREATOR | Chirag Pabbaraju, Ali Vakilian |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-05511