We study the online stochastic bipartite matching problem, in a form
motivated by display ad allocation on the Internet. In the online, but
adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an
approximation ratio of $1-1/e$. In the online, stochastic case when nodes are
drawn repeatedly from a known distribution, the greedy algorithm matches this
approximation ratio, but still, no algorithm is known that beats the $1 - 1/e$
bound.
Our main result is a 0.67-approximation online algorithm for stochastic
bipartite matching, breaking this $1 - {1/e}$ barrier. Furthermore, we show
that no online algorithm can produce a $1-\epsilon$ approximation for an
arbitrarily small $\epsilon$ for this problem.
We employ a novel application of the idea of the power of two choices from
load balancing: we compute two disjoint solutions to the expected instance, and
use both of them in the online algorithm in a prescribed preference order.
To identify these two disjoint solutions, we solve a max flow problem in a
boosted flow graph, and then carefully decompose this maximum flow to two
edge-disjoint (near-)matchings. These two offline solutions are used to
characterize an upper bound for the optimum in any scenario. This is done by
identifying a cut whose value we can bound under the arrival distribution.

本研究介绍了一种算法来解决在线随机二分匹配问题，提供了一个 0.67 的逼近比和一种基于流量图和最大流问题的新方法来解决这个问题。