In a variety of contexts related to Internet advertising, online versions of classic problems such as maximum-weight bipartite matching arise. With internet advertising becoming a multi-billion dollar business, there is a need for algorithms to solve these problems effectively. However, without assumptions on the input distribution, edge weights, order of arrival, etc., no online algorithms for these problems can achieve any bounded competitive ratio.
Fortunately, in many of the advertising contexts where these problems need to be solved, they do satisfy one or more of these assumptions. In this talk, I will present a collection of algorithms with competitive ratios ranging from 1/8 to 1-1/e to 1-\\epsilon, solving problems in ad reservation, display advertising, etc. They also have connections to other well-known problems such as the classical Secretary problem and the Generalized Assignment Problem (GAP). Our algorithms are simple and efficient, making online decisions in essentially linear time (joint work with Martin Pal, Jon Feldman, Vahab Mirrokni, and S. Muthu Muthukrishnan).
