preprint

Learning-Augmented Online Caching: New Upper Bounds

Daniel Skachkov, Denis Ponomaryov, Yuriy Dorn, Alexander Demin

arXiv:2410.01760

Cite this publication

Learning-Augmented Online Caching: New Upper Bounds

@misc{skachkov2024-online-caching,
  title     = {Learning-Augmented Online Caching: New Upper Bounds},
  author    = {Daniel Skachkov and Denis Ponomaryov and Yuriy Dorn and Alexander Demin},
  year      = {2024},
  howpublished = {arXiv},
  note      = {Preprint},
  eprint    = {2410.01760},
  archivePrefix = {arXiv},
  url       = {https://arxiv.org/abs/2410.01760}
}

Download .bib

We address the problem of learning-augmented online caching in the scenario when each request is accompanied by a prediction of the next occurrence of the requested page. We improve currently known bounds on the competitive ratio of the BlindOracle algorithm, which evicts a page predicted to be requested last. We also prove a lower bound on the competitive ratio of any randomized algorithm and show that a combination of the BlindOracle with the Marker algorithm achieves a competitive ratio that is optimal up to some constant.