采用盲算法和最优竞争算法相结合的混合算法在在线缓存中表现优于所有现有方法,而且结构更简单。此外,我们证明了对于这个问题,将 BlindOracle 与 LRU 相结合实际上是确定性算法中的最优解。
May, 2020
本篇论文提出了一种框架,通过将已有的在线算法与机器学习算法结合,可以在具有较低误差的情况下证明实现竞争比的提高。并将此框架应用于传统缓存问题中,通过修改 Marker 算法,利用机器学习算法的预测结果,实现较低的竞争比,即使是使用简单的预测也可以在真实环境中取得好的性能。
Feb, 2018
使用机器学习和加强式算法提高缓存置换的性能
Jun, 2021
设计在线算法,利用机器学习预测,以超越最坏情况范例,解决各种实际相关在线问题(如调度、缓存、聚类、滑雪租赁等)。通过研究设计具备多个专家的在线算法,以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O(log K)性能保证的竞争算法,其中 K 是专家数量,适用于 0-1 在线优化问题。此外,我们的多专家方法提供了一种在线组合多个在线算法的新视角,这是在线算法研究社区长期的核心主题。
Dec, 2023
研究如何将机器学习预测融入在线算法以提高性能,并提供非平凡的下界来衡量竞争分析的最优权衡.
Oct, 2020
本文阐述了一种基于多种算法或预测器的学习增强在线算法技术,通过针对在线问题的分析,设计出与动态组合相竞争的算法,能够在多种预测器之间切换,具有灵活性和实用性。
Apr, 2023
本文提出了一种基于位置定制的缓存方案,使用线性模型估计未来内容命中率,并以此为基础提出了求解最优缓存策略的不依赖于训练的在线算法,实现了自适应缓存决策并达到了与最优策略相当的命中率。
Sep, 2018
研究了使用预测方法改善其性能的在线算法在页面迁移问题上的应用,通过机器学习实现预测精度提高,可实现竞争比接近 1,为算法改进方法的新领域提供了有益的探讨。
Jun, 2020
研究在线非加权二分图匹配中的问题,其中有 n 个离线顶点和 n 个在线顶点,并且希望与最佳离线算法保持竞争力。尽管 Karp 等人 [1990] 的经典 RANKING 算法可以证明达到 1-1/e>1/2 的竞争比率,但我们表明在对抗性到达模型中,没有学习增强方法既可以是 1 - 一致的又可以比 1/2 - 健壮。同时,在随机到达模型下,我们展示了如何利用分布测试方法设计出一种算法,该算法接受关于在线顶点的外部建议,并在竞争比率上从不需要建议的方法和最优比率 1 之间插值,这取决于建议的质量。
May, 2024
在线背包问题的学习增强算法通过使用简洁的预测信息,在无传递完美预测和有限完美预测两种情况下,设计了能够提高算法性能的算法,并在实验中表现优于基线和复杂预测模型的算法。
Jun, 2024