Jun, 2020

带预测的加权页面在线算法

PDF
TL;DR本文研究加权分页问题及其预测，提出 strong per request prediction (SPRP) 模型，证明结合固定的展望和下一个请求数的信息是不足以克服现有的下限。同时，我们还探讨了随着随着预测误差的增加，算法的缓慢衰退。通过一组自然的预测误差度量，给出了上下界。
weighted paging problemonline algorithmspredictionslower boundssprp model
发现论文，激发创造
  • 更好和更简单的学习增强在线缓存

    采用盲算法和最优竞争算法相结合的混合算法在在线缓存中表现优于所有现有方法，而且结构更简单。此外，我们证明了对于这个问题，将 BlindOracle 与 LRU 相结合实际上是确定性算法中的最优解。

    May, 2020

  • 多预测在线算法

    本文研究了在多个机器学习预测的基础上增强的在线算法。我们提出了一个通用的算法框架，用于多重预测的在线覆盖问题，该算法能够获得与最佳预测器性能相竞争的在线解决方案。该算法还能够同时使竞争性达到最佳预测和最佳在线算法的性能水平，并应用于解决一些经典问题。

    May, 2022

  • 带有预测的算法学习

    介绍了一种算法设计范例 —— 基于学习预测器的算法，将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度，在构建优美的预测器的同时，在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果，且提供了第一批基于学习理论的担保。

    Feb, 2022

  • 基于机器学习建议的在线页面迁移

    研究了使用预测方法改善其性能的在线算法在页面迁移问题上的应用，通过机器学习实现预测精度提高，可实现竞争比接近 1，为算法改进方法的新领域提供了有益的探讨。

    Jun, 2020

  • 在线图算法预测

    本文研究具有预测的在线图形问题，提出了一个新的度量误差的定义 (metric error)，并给出了一个通用框架，用于在线预测算法。采用这个框架，我们能够获得关于竞争比率的紧密限制，并将其作为度量误差的函数来描述。

    Dec, 2021

  • 具有不确定性量化预测的在线算法

    如何在设计在线算法中最佳利用不确定性量化预测，以及如何利用更一般形式的不确定性量化，提出了基于在线学习的框架来在多实例场景中学习如何充分利用不确定性量化作出最佳决策。

    Oct, 2023

  • 机器学习建议在线缓存的近最优界限

    该论文研究了基于机器学习建议的在线缓存模型，提出了一种新的算法来解决缓存问题，该算法适用于低误差情况下的预测，具有低的竞争比率；通过改进算法和提供下限，有望进一步提高算法性能。

    Oct, 2019

  • 基于学习预测的在线动态应答

    研究在线动态确认问题及其使用机器学习预测的算法，通过新的预测误差测量，实现同时最优一致性和鲁棒性，可用于其他具有时间特征的在线问题。

    May, 2023

  • 在线零一背包问题的竞争算法与简洁预测

    在线背包问题的学习增强算法通过使用简洁的预测信息，在无传递完美预测和有限完美预测两种情况下，设计了能够提高算法性能的算法，并在实验中表现优于基线和复杂预测模型的算法。

    Jun, 2024

  • 两个世界中的最佳选择：在未知到达模型下的在线资源分配与预测

    给定未知质量的预测作为输入，我们提出了一种算法，在未知预测质量和请求模型的情况下，在在线资源分配问题中实现了渐进最优表现，验证了算法的性能与任何已知到达模型和预测准确性的算法的最佳性能相匹配。

    Feb, 2024