A nonasymptotic analysis for re-solving heuristic in online matching

• 成果类型: Article
• 署名作者: Wang, Hao; Yan, Zhenzhen; Bei, Xiaohui
• 署名单位: Nanyang Technological University
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1111/poms.13738
• 发表日期: 2022
• 页码: 3096-3124
• 关键词: competitive ratio; online bipartite matching; Randomized algorithm; re-solving heuristic

摘要

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.