Improved Analysis of RANKING for Online Vertex-Weighted Bipartite
Matching
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite
Matching
In this paper, we consider the online vertex-weighted bipartite matching problem in the random arrival model. We consider the generalization of the RANKING algorithm for this problem introduced by Huang, Tang, Wu, and Zhang (TALG 2019), who show that their algorithm has a competitive ratio of 0.6534. We show that …