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
Abstract:
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).