Tata Institute of Fundamental Research
Online Matching and Ad Allocation
Colloquium
Speaker:
Aranyak Mehta
Google Research
Mountain View
California
United States of America
Date:
Wednesday, 7 Dec 2011, 14:30 to 15:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The spectacular success of search and display advertising and its huge growth potential has attracted the attention of researchers from many aspects of computer science. A core problem in this area is that of Ad allocation, an inherently algorithmic and game theoretic question - that of matching ad slots to advertisers, online, under demand and supply constraints. Put very simply: the better the matching, the more efficient the market.
The seminal algorithmic work on online matching, by Karp, Vazirani and Vazirani, was done over two decades ago, well before this motivation existed. In this talk, I will present an overview of several key algorithmic papers in this area, starting with its purely academic beginnings, to the general problem motivated by the application. The theory behind these algorithms involves new combinatorial, probabilistic and linear programming techniques. Besides the analytical results, I will also touch upon how these algorithmic ideas can be applied in practice.
| Speaker: | Aranyak Mehta Google Research Mountain View California United States of America |
| Date: | Wednesday, 7 Dec 2011, 14:30 to 15:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The spectacular success of search and display advertising and its huge growth potential has attracted the attention of researchers from many aspects of computer science. A core problem in this area is that of Ad allocation, an inherently algorithmic and game theoretic question - that of matching ad slots to advertisers, online, under demand and supply constraints. Put very simply: the better the matching, the more efficient the market.
The seminal algorithmic work on online matching, by Karp, Vazirani and Vazirani, was done over two decades ago, well before this motivation existed. In this talk, I will present an overview of several key algorithmic papers in this area, starting with its purely academic beginnings, to the general problem motivated by the application. The theory behind these algorithms involves new combinatorial, probabilistic and linear programming techniques. Besides the analytical results, I will also touch upon how these algorithmic ideas can be applied in practice.
The seminal algorithmic work on online matching, by Karp, Vazirani and Vazirani, was done over two decades ago, well before this motivation existed. In this talk, I will present an overview of several key algorithmic papers in this area, starting with its purely academic beginnings, to the general problem motivated by the application. The theory behind these algorithms involves new combinatorial, probabilistic and linear programming techniques. Besides the analytical results, I will also touch upon how these algorithmic ideas can be applied in practice.