本文阐述了一种基于多种算法或预测器的学习增强在线算法技术,通过针对在线问题的分析,设计出与动态组合相竞争的算法,能够在多种预测器之间切换,具有灵活性和实用性。
Apr, 2023
本文研究具有预测的在线图形问题,提出了一个新的度量误差的定义 (metric error),并给出了一个通用框架,用于在线预测算法。采用这个框架,我们能够获得关于竞争比率的紧密限制,并将其作为度量误差的函数来描述。
Dec, 2021
本篇论文提出了一种框架,通过将已有的在线算法与机器学习算法结合,可以在具有较低误差的情况下证明实现竞争比的提高。并将此框架应用于传统缓存问题中,通过修改 Marker 算法,利用机器学习算法的预测结果,实现较低的竞争比,即使是使用简单的预测也可以在真实环境中取得好的性能。
Feb, 2018
该论文研究了基于机器学习建议的在线缓存模型,提出了一种新的算法来解决缓存问题,该算法适用于低误差情况下的预测,具有低的竞争比率;通过改进算法和提供下限,有望进一步提高算法性能。
Oct, 2019
研究在线非加权二分图匹配中的问题,其中有 n 个离线顶点和 n 个在线顶点,并且希望与最佳离线算法保持竞争力。尽管 Karp 等人 [1990] 的经典 RANKING 算法可以证明达到 1-1/e>1/2 的竞争比率,但我们表明在对抗性到达模型中,没有学习增强方法既可以是 1 - 一致的又可以比 1/2 - 健壮。同时,在随机到达模型下,我们展示了如何利用分布测试方法设计出一种算法,该算法接受关于在线顶点的外部建议,并在竞争比率上从不需要建议的方法和最优比率 1 之间插值,这取决于建议的质量。
May, 2024
本文研究加权分页问题及其预测,提出 strong per request prediction (SPRP) 模型,证明结合固定的展望和下一个请求数的信息是不足以克服现有的下限。同时,我们还探讨了随着随着预测误差的增加,算法的缓慢衰退。通过一组自然的预测误差度量,给出了上下界。
Jun, 2020
本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架,用于多重预测的在线覆盖问题,该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平,并应用于解决一些经典问题。
May, 2022
本文提出了适用于任意度量任务系统(MTS)(例如缓存、k-server 和凸体追逐)和在线匹配的预测模型,并利用在线算法理论的结果来展示如何使模型更具鲁棒性,其中特别针对缓存问题,本文提出的算法相对于一般 MTS 问题可使得其性能的预测误差表现成指数级别提升。最后,我们使用实际数据集对所提出的方法进行了实证评估,并得出实用性较好的结论。
Mar, 2020
介绍了一种算法设计范例 —— 基于学习预测器的算法,将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度,在构建优美的预测器的同时,在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果,且提供了第一批基于学习理论的担保。
Feb, 2022
研究如何将机器学习预测融入在线算法以提高性能,并提供非平凡的下界来衡量竞争分析的最优权衡.
Oct, 2020