A nonasymptotic analysis for re‐solving heuristic in online matching

Hao Wang, Zhenzhen Yan and Xiaohui Bei

Production and Operations Management, 2022, vol. 31, issue 8, 3096-3124

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.

Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1111/poms.13738

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:bla:popmgt:v:31:y:2022:i:8:p:3096-3124

Ordering information: This journal article can be ordered from
http://onlinelibrary ... 1111/(ISSN)1937-5956

Access Statistics for this article

Production and Operations Management is currently edited by Kalyan Singhal

More articles in Production and Operations Management from Production and Operations Management Society
Bibliographic data for series maintained by Wiley Content Delivery ().