New and Improved Bounds for Markov Paging
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910251116134400 |
|---|---|
| author | Pabbaraju, Chirag Vakilian, Ali |
| author_facet | Pabbaraju, Chirag Vakilian, Ali |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05511 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New and Improved Bounds for Markov Paging Pabbaraju, Chirag Vakilian, Ali Data Structures and Algorithms 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. |
| title | New and Improved Bounds for Markov Paging |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.05511 |