Online Page Migration with ML Advice
Online Page Migration with ML Advice
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
P. Indyk;Frederik Mallmann-Trenn;Slobodan Mitrovi'c;R. Rubinfeld
中科院分区：
文献类型：
--
作者：
P. Indyk;Frederik Mallmann-Trenn;Slobodan Mitrovi'c;R. Rubinfeld
我们考虑针对{\em页面迁移问题}的在线算法，该算法使用可能不完美的预测来提高其性能。 Westbrook'94 和 Bienkowski 等人'17 提出的针对此问题的最著名的在线算法的竞争比严格限制在 1 范围内。相反，我们表明，如果算法给出输入序列的预测，那么它可以实现趋于 1$ 的竞争比，而预测错误率趋于 0$。具体来说，竞争比等于$1+O(q)$，其中$q$是预测错误率。我们还设计了一个“后备选项”，确保算法对 {\em any} 输入序列的竞争比至多为 $O(1/q)$。我们的结果补充了最近使用机器学习来提高“经典”算法性能的工作。
We consider online algorithms for the {\em page migration problem} that use predictions, potentially imperfect, to improve their performance. The best known online algorithms for this problem, due to Westbrook'94 and Bienkowski et al'17, have competitive ratios strictly bounded away from 1. In contrast, we show that if the algorithm is given a prediction of the input sequence, then it can achieve a competitive ratio that tends to $1$ as the prediction error rate tends to $0$. Specifically, the competitive ratio is equal to $1+O(q)$, where $q$ is the prediction error rate. We also design a ``fallback option'' that ensures that the competitive ratio of the algorithm for {\em any} input sequence is at most $O(1/q)$. Our result adds to the recent body of work that uses machine learning to improve the performance of ``classic'' algorithms.