Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark
Mark Braverman, Mahsa Derakhshan, Antonio Molina Lovett · Proceedings of the 23rd ACM Conference on Economics and Computation · 2022
In this paper, we study max-weight stochastic matchings on online bipartite graphs under both vertex and edge arrivals. We focus on designing polynomial time approximation algorithms with respect to the online benchmark, which was first considered by Papadimitriou, Pollner, Saberi, and Wajc [EC'21].