TY - GEN

T1 - Online stochastic matching

T2 - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009

AU - Feldman, Jon

AU - Mehta, Aranyak

AU - Mirrokni, Vahab

AU - Muthukrishnan, S.

PY - 2009

Y1 - 2009

N2 - 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 ≃ 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/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 - ∈ 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.

AB - 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 ≃ 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/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 - ∈ 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.

UR - http://www.scopus.com/inward/record.url?scp=77952348885&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77952348885&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2009.72

DO - 10.1109/FOCS.2009.72

M3 - Conference contribution

AN - SCOPUS:77952348885

SN - 9780769538501

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 117

EP - 126

BT - Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009

Y2 - 25 October 2009 through 27 October 2009

ER -