Optimal Competitive Ratio of Two-sided Online Bipartite Matching
arXiv:2602.18049
Abstract
We establish an optimal upper bound (negative result) of on the competitive ratio of the fractional version of online bipartite matching with two-sided vertex arrivals, matching the lower bound (positive result) achieved by Wang and Wong (ICALP 2015), and Tang and Zhang (EC 2024).