DIMACS Theoretical Computer Science Seminar

Title: Online Ad Allocation: Adversarial, Stochastic and Simultaneous Approximations

Speaker: Vahab Mirrokni, Google Research in New York

Date: Wednesday, May 2, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


As an important component of any ad serving system, online capacity (or budget) planning is a central problem in online ad allocation. I will survey primal-based and dual-based techniques borrowed from online stochastic matching literature and report theoretical approximation guarantees and practical evaluations of these algorithms on real data sets. Finally, inspired by practical applications, I will discuss a Simultaneous approximation results for both adversarial and stochastic models and present some recent results in this context.

The talk is based on several older papers with colleagues at Google, and two recent WINE11 and SODA12 papers joint with Haeupler(MIT), Oveis Gharan(Stanford), and ZadiMoghaddam(MIT).

See: http://paul.rutgers.edu/~yixinxu/theory-spring12.html