Summary
This work looks at a problem where resources can be reused but become temporarily unavailable when used, with uncertain time durations. The classic Ranking algorithm was known to perform well when resources couldn't be reused, but it was unclear if it could do better than just half the best possible performance when resources can be reused. The authors prove that Ranking actually exceeds this half mark for reusable resources with random durations. They also show how their findings extend to scenarios where resources have different weights or values. Their analysis focuses on each resource’s availability rather than on each request, providing new insights into managing such systems.
What this means in practice
- •For online platform operators: Optimize assignment of reusable assets like rental equipment or shared vehicles under uncertain return times to improve matching efficiency beyond previous 50% benchmarks.
- •For cloud resource schedulers: Improve online scheduling of reusable computational resources with variable release times, achieving better utilization by applying Ranking strategies.
A theory result. No direct application yet.
Abstract
We study online bipartite matching with unit-inventory reusable resources, where requests arrive in an adversarially fixed order, and each use of a resource makes it unavailable for an independent duration drawn from a resource-dependent distribution. The benchmark knows all requests in advance but cannot observe a duration before choosing the corresponding use. The classical Ranking algorithm of Karp, Vazirani, and Vazirani (STOC 1990) fixes a uniformly random priority order of the resources and matches each arriving request to its highest-priority available neighbor. It achieves the optimal competitive ratio $1-1/e$ for unweighted nonreusable resources, but whether it beats $1/2$ for reusable resources has remained open. We prove that, for unweighted resources with resource-dependent stochastic durations, Ranking achieves a competitive ratio of $(5-2\sqrt3)/3\approx0.511966$. We also give a black-box reduction from unweighted Ranking to resource-weighted matching: any unweighted competitive ratio $α>1/2$ yields a weighted ratio strictly above $1/2$. With independent sampling access to the duration distributions, the reduction gives a weighted ratio of $0.500034$. These results resolve two questions left open by Delong et al. (MOR 2024): whether Ranking beats $1/2$, and whether one can beat $1/2$ under stochastic durations. We analyze Ranking resource by resource, rather than request by request. For deterministic durations, this gives a reduction to random-order greedy for a coverage function. We then extend the analysis to stochastic durations by comparing the residual schedules of Ranking and a greedy algorithm, and apply a finer analysis of the random ranks to obtain the stated $0.511$ bound. For the weighted reduction, we apply Ranking within groups of similar weights and uses weighted greedy to control the loss between groups.