论文标题
在线页面迁移带有ML建议
Online Page Migration with ML Advice
论文作者
论文摘要
我们考虑使用预测（可能不完美的预测）来提高其性能的{\ em页面迁移问题}的在线算法。由于Westbrook'94和Bienkowski et al'17，最著名的在线算法的竞争比率严格远离1。相比之下，我们表明，如果算法的预测预测了投入序列，那么它可以达到竞争比率达到预期错误率$ 0 $ 0 $ 0 $ 0 $ 0 $ 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.
