Periodic Reranking for Online Matching of Reusable Resources

Udwani, Rajan. (2022). Periodic Reranking for Online Matching of Reusable Resources. 966-966. 10.1145/3490486.3538344.

We consider a generalization of the vertex weighted online bipartite matching problem where the offline vertices, called resources, are reusable. In particular, when a resource is matched it is unavailable for a deterministic time duration d after which it becomes available for a re-match. Thus, a resource can be matched to many different online vertices over a period of time.

While recent work on the problem has resolved the asymptotic case where we have large starting inventory (i.e., many copies) of every resource, we consider the (more general) case of unit inventory and give the first algorithm that is provably better than the naïve greedy approach which has a competitive ratio of (exactly) 0.5. In particular, we achieve a competitive ratio of 0.589 against an LP relaxation of the offline problem.

Our algorithm generalizes the classic Ranking and Perturbed Greedy algorithms for online matching, by reranking resources over time. While reranking resources frequently has the same worst case performance as greedy, we show that reranking intermittently on a periodic schedule succeeds in addressing reusability of resources and performs significantly better than greedy in the worst case.