Online Stochastic Matching: Beating 1-1/e

By Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, S. Muthu Muthukrishnan. 2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

370 citations recorded by the source corpus.

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\over e} \simeq 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 - {1\over e}$ bound.Our main result is a $0.67$-approximation online algorithm for stochastic bipartite matching, breaking this $1 - {1\over e}$ barrier. Furthermore, we show that no online algorithm can produce a $1-\epsilon$ approximation for an arbitrarily small $\epsilon$ 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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/f7242650479471b789372241267d509cb80ec64e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

  1. Aranyak Mehta
  2. Mohammad Mahdian
  3. Qiqi Yan
  4. Yinyu Ye
  5. Stephen P. Boyd

In Computer Networks and Communications

  1. Aranyak Mehta
  2. Qiqi Yan
  3. Mohammad Mahdian
  4. Yinyu Ye
  5. Zizhuo Wang
  6. Shipra Agrawal
  7. J. Dattorro
  8. Chien-Ju Ho

In Management Science and Operations Research

  1. Aranyak Mehta
  2. Qiqi Yan
  3. Mohammad Mahdian
  4. Yinyu Ye
  5. Zizhuo Wang
  6. Shipra Agrawal
  7. Mengdi Wang
  8. Benjamin Van Roy

Citations in the corpus