论文标题
通过流体近似指导的算法在线分配可重复使用的资源
Online Allocation of Reusable Resources via Algorithms Guided by Fluid Approximations
论文作者
论文摘要
我们考虑可重复使用的资源的在线分配（匹配和分类）的问题，其中客户以对抗性方式依次到达，并在随机持续时间内使用或租用分配的资源，该持续时间独立于已知的分布。为了关注大量库存的情况，我们提供了一种算法，即$（1-1/e）$竞争一般使用分布。我们结果的核心是一种放松的在线算法的概念，该算法仅受到问题中随机元素的流体近似。该算法的输出是最终算法的指南。这导致了在线资源分配问题中无缝解决随机元素（例如可重复性，客户选择和其组合）的原则方法，这可能更广泛地有用。
We consider the problem of online allocation (matching and assortments) of reusable resources where customers arrive sequentially in an adversarial fashion and allocated resources are used or rented for a stochastic duration that is drawn independently from known distributions. Focusing on the case of large inventory, we give an algorithm that is $(1-1/e)$ competitive for general usage distributions. At the heart of our result is the notion of a relaxed online algorithm that is only subjected to fluid approximations of the stochastic elements in the problem. The output of this algorithm serves as a guide for the final algorithm. This leads to a principled approach for seamlessly addressing stochastic elements (such as reusability, customer choice, and combinations thereof) in online resource allocation problems, that may be useful more broadly.
