Online Stochastic Packing Applied to Display Ad Allocation

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0


19 pages, 3 figures, 3 tables. The new version generalizes results to a broader class of packing problems, and gives additiona

Scientific paper

Inspired by online ad allocation, we study online stochastic packing linear programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing linear programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple primal-dual training-based algorithm achieves a (1 - o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1 - 1/e for online ad allocation, and \log m for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based primal-dual algorithms on real data sets, and also indicate an intrinsic trade-off between fairness and efficiency.

No associations


Say what you really think

Search for scientists and scientific papers. Rate them and share your experience with other people.


Online Stochastic Packing Applied to Display Ad Allocation 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 Packing Applied to Display Ad Allocation, we encourage you to share that experience with our community. Your opinion is very important and Online Stochastic Packing Applied to Display Ad Allocation will most certainly appreciate the feedback.

Rate now


Profile ID: LFWR-SCP-O-253966

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.