  Online bipartite matching with edge arrivals remained a major open question
for a long time until a recent negative result by [Gamlath et al. FOCS 2019],
who showed that no online policy is better than the straightforward greedy
algorithm, i.e., no online algorithm has a worst-case competitive ratio better
than $0.5$. In this work, we consider the bipartite matching problem with edge
arrivals in a natural stochastic framework, i.e., Bayesian setting where each
edge of the graph is independently realized according to a known probability
distribution.
  We focus on a natural class of prune & greedy online policies motivated by
practical considerations from a multitude of online matching platforms. Any
prune & greedy algorithm consists of two stages: first, it decreases the
probabilities of some edges in the stochastic instance and then runs greedy
algorithm on the pruned graph. We propose prune & greedy algorithms that are
$0.552$-competitive on the instances that can be pruned to a $2$-regular
stochastic bipartite graph, and $0.503$-competitive on arbitrary bipartite
graphs. The algorithms and our analysis significantly deviate from the prior
work. We first obtain analytically manageable lower bound on the size of the
matching, which leads to a non linear optimization problem. We further reduce
this problem to a continuous optimization with a constant number of parameters
that can be solved using standard software tools.
