Online Bipartite Matching via Smoothness

03/24/2022
by   Jason Hartline, et al.
0

The analysis of online bipartite matching of Eden et al. (2021) is a smoothness proof (Syrgkanis and Tardos, 2013). Moreover, it can be interpreted as combining a λ = 1-1/e value covering (which holds for single-dimensional agents and randomized auctions) and μ = 1 revenue covering (Hartline et al., 2014). Note that value covering is a fact about single-dimensional agents and has nothing to do with the underlying feasibility setting. Thus, the essential new result from Eden et al. (2021) is that online bipartite matching is μ=1 revenue covered.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset