论文标题
在线分配可重复使用的资源的渐近最佳竞争比率
Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
论文作者
论文摘要
我们考虑可重复使用的资源的在线分配（匹配，预算分配和分类）的问题，在这些资源中，对对抗性的资源请求顺序会随着时间的推移而揭示，并且任何分配的资源都会在与资源相关用法分布独立绘制的随机持续时间内使用/出租。以前，众所周知，贪婪的算法对千里眼的基准是0.5竞争性的，该基准事先知道了整个请求序列（Gong等人（2021））。我们给出了一种新颖的算法，即$（1-1/e）$ - 当每个资源的起始容量较大并且已知使用分布时，对于任意使用分布而有竞争力。这是该问题的最佳竞争比率保证，即，没有在线算法可以具有更好的竞争比率。我们还提供了一种发行的在线算法，并表明它是$（1-1/e）$ - 在特殊情况下具有竞争力。我们算法的核心是一种新数量，它通过（计算上）在资源的相同单元之间产生不对称性来影响每个资源可重复使用的潜力。我们通过为新型不平等系统构建可行的解决方案来建立算法的性能保证，该解决方案允许与千里眼的基准直接比较基准的线性编程（LP）放松基准。我们的技术概括了在线资源分配的原始二偶分析框架，并且可能引起更广泛的兴趣。
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 any allocated resource is used/rented for a stochastic duration drawn independently from a resource dependent usage distribution. Previously, it was known that a greedy algorithm is 0.5--competitive against the clairvoyant benchmark that knows the entire sequence of requests in advance (Gong et al. (2021)). We give a novel algorithm that is $(1-1/e)$--competitive for arbitrary usage distributions when the starting capacity of each resource is large and the usage distributions are known. This is the best achievable competitive ratio guarantee for the problem, i.e., no online algorithm can have better competitive ratio. We also give a distribution oblivious online algorithm and show that it is $(1-1/e)$--competitive in special cases. At the heart of our algorithms 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. We establish the performance guarantee for our algorithms by constructing a feasible solution to a novel system of inequalities that allows direct comparison with the clairvoyant benchmark instead of a linear programming (LP) relaxation of the benchmark. Our technique generalizes the primal-dual analysis framework for online resource allocation and may be of broader interest.
