Algorithms for Online Stochastic Ad Allocation

Computer Science and Engineering
NYU Community Event


Vahab Mirrokni, Google


As an important part of any ad delivery system, online ad serving is a rich source of challenging algorithmic and stochastic optimization problems capturing online stochastic matching problems. In this talk, I will survey recent algorithmic results in this area. In particular, we will discuss both adversarial and stochastic iid and random-order models and present:

  • a 0.67-approximation for the online stochastic matching problem in the iid model with known distributions, improving the approximation factor of 1-1/e;
  • a training-based (1-epsilon)-approximation for a general class of packing-covering linear programs in the random-order model under some assumptions; and
  • a (1-1/e)-approximation algorithm for a general class of stochastic assignment problems in the adversarial model with free disposal.

Throughout the talk, we use primal-dual and power-of-two-choices techniques for the design and analysis of the algorithms.


Vahab Mirrokni is a Senior Research Scientist at Google Research in New York. He joined Google after receiving a B.Sc. from Sharif University in 2001 and a Ph.D. from MIT in 2005, one year at MIT and, and two years at Microsoft Research. Vahab is co-winner of the SODA 2005 best student paper  award and the ACM EC 2008 best paper award. Vahab's research interests include algorithms, algorithmic game theory, and Internet Economics. At Google, he is working on various algorithmic and economic problems related to internet search and online advertisement.