AdWords and Generalized On-line Matching

Amin Saberi
Department of Management Science and Engineering and
  Institute for Computational and Mathematical Engineering
Stanford University


Wednesday, February 9, 2005
4:45 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

The internet search business relies upon an innovative auction market in search key-words to sell advertisements. Advertisers place bids for keywords subject to their maximum daily budget. In this talk we consider the resulting computational problem: assign queries to advertisers (online) to maximize revenues. This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive two algorithms achieving competitive ratios of 1-1/e for this problem. We will also discuss several open problems in this direction. Joint work with A. Mehta, U. Vazirani and V. Vazirani.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html