Adwords and Generalized Online Matching

Search engine companies have revolutionized the use of the Internet by individuals. Their dramatic revenues are supported by an interesting innovation: in the way businesses advertise to consumers. I will talk about this innovation and the underlying computational problem it raises. The latter is an elegant generalization of the online bipartite matching problem. We give two optimal algorithms for this problem, each achieving a competitive ratio of 1-1/e. The design of these algorithms is made possible by the new notion of tradeoff-revealing linear programs. This is joint work with Amin Saberi, Umesh Vazirani and Vijay Vazirani.