一种统一的离线 - 在线资源分配的双阶段模型
这篇论文提出了一种新的在线匹配模型,该模型考虑了资源重用问题,同时给出了一个基于线性规划的自适应算法,可以在应用实例如出租车调度服务等中得到应用。
Nov, 2017
给定未知质量的预测作为输入,我们提出了一种算法,在未知预测质量和请求模型的情况下,在在线资源分配问题中实现了渐进最优表现,验证了算法的性能与任何已知到达模型和预测准确性的算法的最佳性能相匹配。
Feb, 2024
我们在本文中解决了一种带有任务转移的在线网络资源分配问题,提出了基于指数加权方法的随机在线算法,证明了该算法具有次线性时间后悔,通过对人工数据进行性能测试并与强化学习方法进行比较表明我们的方法优于后者。
Nov, 2023
本文研究了一个在线资源预订问题,通过一个由两个计算节点组成的通信网络,在有限时间内最小化整体预订成本,并且保持累计违规与运输成本在一定预算限制下的在线重复博弈,提出了一个在线鞍点算法来解决该问题。
May, 2023
本文研究了一个多期的长期资源分配问题,其中每个周期需要一个多阶段的决策过程。我们将此问题定义为具有未知非平稳转换和随机非平稳奖励和资源消耗函数的离散时段有限马尔可夫决策过程的在线资源分配问题。我们提出了一种基于占用度量的等效在线线性规划重构方法,并开发了一种在线镜像下降算法。我们证明,在随机奖励和资源消耗函数下,在线镜像下降算法的期望遗憾值受到了限制。
May, 2023
本文提出一种针对多个资源分配问题的算法体系,将在线请求建模为每次从未知的概率分布中独立抽取,给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法,并且探究了如何在任意情况下应对敌对分布。同时,文中提出了解决大型 LPs 混合装填覆盖问题的快速算法,并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。
Mar, 2019
研究了在线分配问题,通过创建不对称性来控制重用性引起的随机依赖,并建立了一个新算法,获得了最佳竞争比率。(The paper studies the problem of online allocation and proposes a new algorithm that creates asymmetry to control the stochastic dependencies induced by reusability, achieving the best possible competitive ratio.)
Feb, 2020
我们探索了一种用于动态公平资源分配问题的主动学习方法,该方法假设在在线资源分配过程的每个时期,仅从选择的代理人子集中获取反馈。尽管存在这种限制,我们提出的算法在包括资源分配问题中常用的公平度量和匹配机制中的稳定性考虑等各种度量中,提供了与时间周期数次线性相关的后悔界限。我们算法的关键洞察在于通过利用对决性的上限和下限置信区间来自适应地识别最具信息量的反馈。通过这种策略,我们证明高效的决策不需要大量的反馈,并为各种问题类别产生高效的结果。
Jun, 2024