Online Algorithms for Weighted Paging with Predictions
Online Algorithms for Weighted Paging with Predictions
复制标题
DOI：
10.1145/3548774
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Zhihao Jiang;Debmalya Panigrahi;Kevin Sun
中科院分区：
文献类型：
--
作者：
Zhihao Jiang;Debmalya Panigrahi;Kevin Sun
在本文中，我们启动了对预测加权分页问题的研究。这延续了在线算法中的最新作品，并进行了预测，尤其是Lykouris和Vassilvitski（ICML 2018）和Rohatgi（苏打水2020年）对未加权的分页进行预测。我们表明，与未加权的分页不同，固定的lookahead和每个页面的下一个请求都不是足够的信息来克服加权分页中现有的下限。但是，这两者的组合（我们称为强烈的请求预测（SPRP））足以给出2竞争性算法。我们还探讨了随着预测误差的增加而优雅地退化算法的问题，并为一组自然预测误差的自然测量提供了上限和下限。
In this article, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor a knowledge of the next request for every page is sufficient information for an algorithm to overcome the existing lower bounds in weighted paging. However, a combination of the two, which we call strong per request prediction (SPRP), suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error.