Aranyak Mehta, Google Research, Mountain View.
Location and Time: KACB 1116E, Thur, Feb 24, 4:30pm.
Host: V. Vazirani (please contact V.V. to meet with the speaker)
------------------------------
Online Matching and the Adwords Market
------------------------------
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).
No comments:
Post a Comment