Paper Info
Title
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model
Abstract
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 [9], who show that their algorithm has a competitive ratio of 0.6534. We show that assumptions in their analysis can be weakened, allowing us to replace their derivation of a crucial function g on the unit square with a linear program that computes the values of a best possible g under these assumptions on a discretized unit square. We show that the discretization does not incur much error, and show computationally that we can obtain a competitive ratio of 0.6629. To compute the bound over our discretized unit square we use parallelization, and still needed two days of computing on a 64-core machine. Furthermore, by modifying our linear program somewhat, we can show computationally an upper bound on our approach of 0.6688; any further progress beyond this bound will require either further weakening in the assumptions of g or a stronger analysis than that of Huang et al.
Year
DOI
Venue
2021
10.1007/978-3-030-94676-0_12
WEB AND INTERNET ECONOMICS, WINE 2021
Keywords
DocType
Volume
Bipartite matching, Online algorithms
Conference
13112
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Billy Jin100.34
David P. Williamson23564413.34