STOC'13 Workshop, June 1st, 2013
Nikhil Devanur, Microsoft Research, MountainView
Vahab Mirrokni, Google Research, New York
Online advertising is a fast growing business on the Internet with tens of billions of dollars in annual revenue. Online ads appear in various forms such as sponsored search ads, contextual ads, and
display or graphical ads. An important part of all advertising systems which are delivering various types of ads is the ad serving or ad delivery component that decides on the set of ads to show to users for their online activities like search, watching videos, or surfing the web.
Motivated by such applications, there has been a rich theory of online algorithms for many problems, from the basic bipartite matching to more general resource allocation problems, in a variety of models, including the worst-case competitive analysis and many stochastic models. This has also been a exemplary case of theory being applied to and having an impact on important practical problems.
In this workshop, we plan to survey key theoretical results in this area and practical applications of these results, and pose some new research directions and open problems.