A nonasymptotic analysis for re-solving heuristic in online matching

• Main Authors: Wang, Hao, Yan, Zhenzhen, Bei, Xiaohui
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2022
• Subjects: Science::Physics; Competitive Ratio; Online Bipartite Matching
• Online Access: https://hdl.handle.net/10356/162741
• Institution: Nanyang Technological University

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 ge...