Paper Info
Title
Online stochastic matching: online actions based on offline statistics
Abstract
We consider the online stochastic matching problem proposed by Feldman et al. [4] as a model of display ad allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bins and the other side represents the set of possible ball types. At each time step, a ball is sampled independently from the given distribution and it needs to be matched upon its arrival to an empty bin. The goal is to maximize the size of the matching. We present an online algorithm for this problem with a competitive ratio of 0.702. Before our result, algorithms with a competitive ratio better than 1−1/e were known under the assumption that the expected number of arriving balls of each type is integral. A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling and use those statistics to guide the decisions of the online algorithm. We also show that no online algorithm can have a competitive ratio better than 0.823.
Year
DOI
Venue
2011
10.1287/moor.1120.0551
SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms San Francisco California January, 2011
Keywords
DocType
Volume
known distribution model,competitive ratio,permutation model,hardness side,empty bin,mehta a,feldman j,monte carlo sampling,online stochastic matching,offline statistic,random input model,online algorithm,possible ball type,bipartite graph,fixed set,display ad allocation,online action,offline statistics,online stochastic,graph corresponds,randomized algorithms,distributed computing,leader election
Conference
37
Issue
ISSN
ISBN
4
0364-765X
978-1-61197-251-1
Citations 
PageRank 
References 
26
1.43
13
Authors
3
Name
Order
Citations
PageRank
Vahideh Manshadi1587.30
Shayan Oveis Gharan232326.63
Amin Saberi32824224.27