Online Stochastic Matching: Beating 1-1/e
Authors:
- Jon FeldmanJFJon Feldman
- Aranyak MehtaAMAranyak Mehta
- Vahab MirrokniVMVahab Mirrokni
- S. MuthukrishnanSMS. Muthukrishnan
- 1 October 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 117-126
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- 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 - ¿ barrier. Furthermore, we show that no online algorithm can produce a 1 - ¿ approximation for an arbitrarily small e 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.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- The adwords problem2009
- Budgeted Allocations in the Full-Information SettingLecture Notes in Computer Science, 2008
- On-line bipartite matching made simpleACM SIGACT News, 2008
- Improved Approximation Algorithms for Budgeted Allocations2008
- Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue2007
- Allocating online advertisement space with unreliable estimates2007
- Approximation algorithms for dynamic resource allocationOperations Research Letters, 2006
- On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic ProgrammingMathematics of Operations Research, 2004
- The power of two choices in randomized load balancingIEEE Transactions on Parallel and Distributed Systems, 2001
- Balanced AllocationsSIAM Journal on Computing, 1999