Metraipolis › archive › dc_d2e57ddf60b5

Tight Lower Bounds for Distributional Paging — arXiv:2610.40824

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.40824
License (as archived)
CC0-1.0
Archived
2026-11-03T05:49:18.522Z
SHA-256 of the archived text
b6964bd19151f4cb5c066a3c24cdf0d890060735bd8b6c998e229c3b5314622e
Stable URL of this page
https://metraipolis.com/documento/dc_d2e57ddf60b5

How to cite

Tight Lower Bounds for Distributional Paging — arXiv:2610.40824 — arXiv (en), https://arxiv.org/abs/2610.40824 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d2e57ddf60b5 (Metraipolis archive dc_d2e57ddf60b5, sha256 b6964bd19151f4cb5c066a3c24cdf0d890060735bd8b6c998e229c3b5314622e)
BibTeX
@misc{dcd2e57ddf60b5,
  title = {Tight Lower Bounds for Distributional Paging — arXiv:2610.40824},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40824},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d2e57ddf60b5; sha256 b6964bd19151f4cb5c066a3c24cdf0d890060735bd8b6c998e229c3b5314622e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40824. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Distributional paging seeks a polynomial-time eviction rule that competes with the optimal \emph{online} policy $\mathrm{OPT}$ when requests come from a known stochastic source. Two algorithms by Lund, Phillips, and Reingold [FOCS, 1994] are canonical. Their randomized \emph{dominating distribution} algorithm, for Markov sources, evicts a page drawn from a distribution over the cache satisfying pairwise linear inequalities; their deterministic \emph{median} algorithm, for sources with independent inter-arrival times across pages, evicts the cached page with the largest lower median of its conditional next-request time. Their original guarantees of $4$ and $5$ were recently improved to $2$ and $4$ by Pabbaraju and Vakilian [ICALP 2025]. We show that neither improved constant can be reduced in its respective source model. For Markov paging, we give two complementary factor-$2$ lower-bound constructions, each with an explicit polynomial-time dominating selector. A directed-cycle family has ratio $2k/(k+1)$, while a recurrent four-page family with cache size three has ratio $2-4\varepsilon/3$. For the independent inter-arrival model, we show that the median algorithm is not $c$-competitive for any $c<4$. These are separate results for distinct stochastic models. Matching the known upper bounds, they establish tight competitive ratios of $2$ and $4$, respectively, improving on previous lower bounds of $1.5907$ and $1.511$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.40824 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:34:47.014Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).