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.
N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.
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 -