Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources

Goyal, V., Iyengar, G., & Udwani, R. (2020). Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources.

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.