A nonasymptotic analysis for re-solving heuristic in online matching

Production and Operations Management · 2022 · Volume 31 · Issue 8

Abstract

We investigate an online edge-weighted bipartite matching problem with general capacity constraints. In this problem, the resources are offline and nonreplenishable with different capacities. Demands arrive online and each requests a certain amount of resources. The goal is to maximize the reward generated by successful matches. We model the offline optimization problem as a deterministic linear program (LP) and present multiple randomized online algorithms based on the solution to the offline LP. We analyze the performance guarantee of each algorithm in terms of its competitive ratio (CR). Importantly, we introduce a re-solving heuristic that periodically recomputes the offline LP and uses the updated offline solution to guide the online algorithm decisions. We find that the algorithm's CR can be significantly improved when re-solving at carefully selected time steps. Finally, we investigate the value of the demand distribution in further improving the algorithm efficiency. We conduct extensive numerical studies to demonstrate the efficiency of the proposed algorithms. The effect of market conditions on the algorithm performance is also investigated.

Keywords

competitive ratio, online bipartite matching, randomized algorithm, re-solving heuristic

Enable JavaScript for citation tools and additional paper interactions.