Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/162741
Title: A nonasymptotic analysis for re-solving heuristic in online matching
Authors: Wang, Hao
Yan, Zhenzhen
Bei, Xiaohui
Keywords: Science::Physics
Issue Date: 2022
Source: Wang, H., Yan, Z. & Bei, X. (2022). A nonasymptotic analysis for re-solving heuristic in online matching. Production and Operations Management, 31(8), 3096-3124. https://dx.doi.org/10.1111/poms.13738
Project: RG17/21
MOE2019-T2-1-045(S)
Journal: Production and Operations Management
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.
URI: https://hdl.handle.net/10356/162741
ISSN: 1059-1478
DOI: 10.1111/poms.13738
Rights: © 2022 Production and Operations Management Society. This is the author's version of the work. It is posted here by permission of Production and Operations Management Society for personal use, not for redistribution. The definitive version was published in Production and Operations Management, 31( 8), 3096-3124. https://doi.org/10.1111/poms.13738.
Fulltext Permission: embargo_20240907
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
A nonasymptotic analysis for resolving heuristic in online matching.pdf
  Until 2024-09-07
1.23 MBAdobe PDFUnder embargo until Sep 07, 2024

Page view(s)

17
Updated on Dec 2, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.