BriefGPT.xyz
Feb, 2018
机器学习建议下的竞争性缓存
Competitive caching with machine learned advice
HTML
PDF
Thodoris Lykouris, Sergei Vassilvitskii
TL;DR
本篇论文提出了一种框架,通过将已有的在线算法与机器学习算法结合,可以在具有较低误差的情况下证明实现竞争比的提高。并将此框架应用于传统缓存问题中,通过修改Marker算法,利用机器学习算法的预测结果,实现较低的竞争比,即使是使用简单的预测也可以在真实环境中取得好的性能。
Abstract
Traditional
online algorithms
encapsulate decision making under uncertainty, and give ways to hedge against all possible future events, while guaranteeing a nearly optimal solution as compared to an offline optimum. On the other hand,
→