Competitive Ratio of Online Caching with Predictions: Lower and Upper Bounds
<|reference_start|>Competitive Ratio of Online Caching with Predictions: Lower and Upper Bounds: 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.<|reference_end|>
@article{skachkov2024competitive,
    title={Competitive Ratio of Online Caching with Predictions: Lower and Upper
  Bounds},
    author={Daniel Skachkov, Denis Ponomaryov, Yuri Dorn, and Alexander Demin},
    journal={arXiv preprint arXiv:2410.01760},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.01760},
    primaryClass={cs.DB}
}