Online Stochastic Matching with Edge Arrivals
share
Online bipartite matching with edge arrivals is an important extension of the classic vertex-arrival model of Karp, Vazirani and Vazirani. Finding an algorithm better than the straightforward greedy strategy remained a major open question for a long time until a recent negative result by Gamlath et al. (forthcoming FOCS 2019), who showed that no online algorithm has a competitive ratio better than 0.5 in the worst case. In this work, we consider the bipartite matching problem with edge arrivals in the stochastic framework. We find an online algorithm that on average is 0.506-competitive. We give a supplementary upper bound of 2/3 and also obtain along the way an interesting auxiliary result that if the initial instance has a 2-regular stochastic subgraph, then a natural prune greedy algorithm matches at least 0.532-fraction of all vertices.
READ FULL TEXT