Georgia Institute of Technology College of Sciences

The spectacular success of search and display advertising -- to businesses and search engine companies -- and its huge growth potential has attracted the attention of researchers from many aspects of computer science. Since a core problem in this area is that of effective ad allocation, an inherently algorithmic and game-theoretic question, numerous theoreticians have worked in this area in recent years. Ad allocation involves matching ad slots to advertisers, under demand and supply constraints. In short, the better the matching, the more efficient the market. Interestingly, the seminal work on online matching, by Karp, Vazirani and Vazirani, was done over two decades ago, well before the advent of the Internet economy! In this talk, I will give an overview of several key algorithmic papers in this area, starting with its purely academic beginnings, to papers that actually address the Adwords problem. The elegant -- and deep -- theory behind these algorithms involves new combinatorial, probabilistic and linear programming techniques. Besides the classic KVV paper (STOC 1990), this talk will refer to several papers with my co-authors: Mehta, Saberi, Vazirani, Vazirani (FOCS 05, J. ACM 07), Goel, Mehta (SODA 08), Feldman, Mehta, Mirrokni, Muthukrishnan (FOCS 09), Aggarwal, Goel, Karande, Mehta (SODA 10), Karande, Mehta, Tripathi (STOC 11).