# Online Stochastic Matching: Beating 1-1/e

### Venue

Symposium on the Foundations of Computer Science (FOCS) (2009)

### Publication Year

2009

### Authors

Jon Feldman, Aranyak Mehta, Vahab Mirrokni, S. Muthukrishnan

### BibTeX

## Abstract

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−1e≃0.632, a very familiar bound that holds for many online problems; further, the
bound is tight in this case. 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−1e bound.Our
main result is a 0.67-approximation online algorithm for stochastic bipartite
matching, breaking this 1−1e barrier. Furthermore, we show that no online algorithm
can produce a 1−ϵ approximation for an arbitrarily small ϵ for this problem. Our
algorithms are based on computing an optimal offline solution to the expected
instance, and using this solution as a guideline in the process of online
allocation. 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. In addition to guiding the online decision making, 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. At the end, we discuss extensions of our results to more
general bipartite allocations that are important in a display ad application.