Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources

Vineet Goyal (), Garud Iyengar () and Rajan Udwani ()
Additional contact information
Vineet Goyal: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Garud Iyengar: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Rajan Udwani: Department of Industrial Engineering and Operations Research, University of California Berkeley, Berkeley, California 94720

Operations Research, 2025, vol. 73, issue 4, 1897-1915

Abstract: We consider the problem of online allocation (matching, budgeted allocations, and assortments) of reusable resources for which 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. 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; that is, no online algorithm can have a 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 relaxation of the benchmark. Our technique generalizes the primal-dual analysis framework for online resource allocation and may be of broader interest.

Keywords: Market; Analytics; and; Revenue; Management; online resource allocation; reusable resources; primal-dual; optimal competitive ratio (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0695 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:4:p:1897-1915

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().