We consider the problem of online allocation (matching, budgeted allocations, and assortments) of reusable resources where an adversarial sequence of resource requests is revealed over time and allocated resources are used/rented for a stochastic duration, drawn independently from known resource usage distributions. This problem is a fundamental generalization of well studied models in online matching and resource allocation. We give an algorithm that obtains the best possible competitive ratio of $(1-1/e)$ for general usage distributions and large resource capacities. At the heart of our algorithm is a new quantity that factors in the potential of reusability for each resource by (computationally) creating an asymmetry between identical units of the resource. In order to control the stochastic dependencies induced by reusability, we introduce a relaxed online algorithm that is only subject to fluid approximations of the stochastic elements in the problem. The output of this relaxed algorithm guides the overall algorithm. Finally, we establish competitive ratio guarantees by constructing a feasible solution to an LP free system of constraints. More generally, these ideas lead to a principled approach for integrating stochastic and combinatorial elements (such as reusability, customer choice, and budgeted allocations) in online resource allocation problems.


翻译:我们考虑的是在线分配(匹配、预算分配和各种类别)可再使用资源的在线分配问题(匹配、预算分配和各种),在这种资源请求的对抗性序列随时间而披露,而且分配的资源被使用/租赁用于与已知资源使用分配无关的随机性期限,与已知资源使用分配无关;这是在网上匹配和资源分配方面对经过周密研究的模型进行根本性的概括化。我们给出了一种算法,在一般使用分配和大量资源能力方面,获得尽可能最佳的1美元(1/1/e)的竞争性比率。在我们的算法的核心是一个新的数量,它由于(推定的)在资源相同单位之间造成不对称,从而有可能使每种资源重新出现重复的可能性。为了控制因可重复性而引起的随机性依赖性依赖性,我们引入了一种简单的在线算法,它只取决于问题中随机性要素的流近。这种宽松的算法产出指导了总体算法。最后,我们通过为LP自由约束系统构建一个可行的解决方案来建立竞争性比率保障。更一般地说,这些想法导致一种原则性的方法,将客户选择和在线分配中的资源分配(例如可重新确定资源分配)。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
52+阅读 · 2020年9月7日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
18+阅读 · 2019年2月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
18+阅读 · 2019年2月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员