Computer Science – Data Structures and Algorithms
Scientific paper
2010-07-09
Computer Science
Data Structures and Algorithms
Scientific paper
We consider the online stochastic matching problem proposed by Feldman et al. [FMMM09] 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 number of allocations. 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 our algorithm achieves a competitive ratio of 0.705 when the rates are integral. On the hardness side, we prove that no online algorithm can have a competitive ratio better than 0.823 under the known distribution model (and henceforth under the permutation model). This improves upon the 5/6 hardness result proved by Goel and Mehta \cite{GM08} for the permutation model.
Gharan Shayan Oveis
Manshadi Vahideh H.
Saberi Amin
No associations
LandOfFree
Online Stochastic Matching: Online Actions Based on Offline Statistics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Stochastic Matching: Online Actions Based on Offline Statistics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Stochastic Matching: Online Actions Based on Offline Statistics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-299906