AAAIFeb, 2024

学习增强的二层滑雪租赁问题的在线算法

PDF
TL;DR我们研究了两层滑雪租借问题，其中用户需要通过选择三个支付选项之一来满足多个项目的一系列需求：按需使用支付（即租赁），购买单个项目（即单独购买）和购买所有项目（即组合购买）。我们设计了一种稳健的在线算法（RDTSR），它能提供最坏情况下的性能保证。为了兼顾在线算法的稳健性和机器学习的平均性能，我们开发了一种学习增强算法（LADTSR），通过将机器学习预测集成到稳健的在线算法中，即使预测不准确也能确保最坏情况下的性能保证。最后，我们对合成数据和真实迹线数据进行了数值实验以验证我们方法的有效性。
ski-rental problemtwo-levelonline algorithmmachine learninglearning-augmented algorithm
发现论文，激发创造
  • 关于学习增强的多选项滑雪租赁的最佳一致性 - 鲁棒性权衡

    本研究解决了学习增强的多选项滑雪租借问题，提出了最佳算法来匹配已知的下界，为随机算法提供了第一个非平凡的下界并呈现了一个改进的随机算法。

    Dec, 2023

  • 基于回归的增强学习在线算法

    本文介绍了在学习增强的在线算法中使用回归技术来预测未来输入参数的方法，并在广义滑雪租赁、装箱问题、最小完成时间调度等一般在线搜索方案的背景下探讨了这种方法。通过在设计回归问题的损失函数中结合在线优化基准，我们显示了这种回归问题样本复杂度的近似上下界，并将我们的结果扩展到了不可知设置。

    May, 2022

  • 学习增强在线算法的最优韧性 - 一致性平衡

    研究如何将机器学习预测融入在线算法以提高性能，并提供非平凡的下界来衡量竞争分析的最优权衡.

    Oct, 2020

  • 学习增强的在线时间信息和传输成本最小化

    考虑到离散时间系统中的资源受限源，通过时变无线信道将其时间敏感的数据传输到目的地。我们开发了一种鲁棒的在线算法，以最小化传输和信息老化成本之和，确保最坏情况下的性能保证。

    Mar, 2024

  • 在线斯坦纳树学习增强算法

    本文考虑了将机器学习与在线算法设计相结合的新型 “超越最坏情况” 算法分析模型在在线 Steiner 树问题上的应用，其中预测的终端节点可能不正确，算法性能取决于错误预测的数量，可以通过正确预测来突破在线下界并且具有良好的竞争比，同时实验证明该理论具有预测性。

    Dec, 2021

  • 多专家在线覆盖

    设计在线算法，利用机器学习预测，以超越最坏情况范例，解决各种实际相关在线问题（如调度、缓存、聚类、滑雪租赁等）。通过研究设计具备多个专家的在线算法，以超越静态最佳专家的贪心基准。在新的动态基准中提出了具有 O（log K）性能保证的竞争算法，其中 K 是专家数量，适用于 0-1 在线优化问题。此外，我们的多专家方法提供了一种在线组合多个在线算法的新视角，这是在线算法研究社区长期的核心主题。

    Dec, 2023

  • 学习使用 Bandit 反馈调度在线任务

    提出了一种基于双重乐观学习的 Robbins-Monro 算法来解决在线任务调度中不确定任务到达分布和未知奖励与成本问题。通过在决策过程中利用乐观估计奖励与成本比例和 Robbins-Monro 方法隐式学习任务到达分布，DOL-RM 算法在不同不确定性环境下实现了有效的调度，并取得了比其他先进基准方法更好的累积奖励与成本比。

    Feb, 2024

  • 基于学习的算法展开技术用于带预算约束的在线优化

    本文提出了一种新的机器学习辅助在线优化算法，并通过引入 Lagrangian 倍增方法，在线更新约束条件优化准则，实现在多个限制条件下进行深度学习模型联合优化，避免了现有算法的缺陷，提高了算法效率和性能。

    Dec, 2022

  • 在线算法的机器学习预测定制化

    本研究探讨在机器学习算法中加入优化基准以提高在线算法的预测性能，以租赁或购买问题为例，并通过理论边界和数值模拟能够支持此发现。

    May, 2022

  • 更好和更简单的学习增强在线缓存

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

    May, 2020