| Report ID: | 05-09-01 |
| Initial Submission Date: | 2005-09-14 |
| Title: | Adwords and Generalizad Online Matching |
| Summary: | How does a search engine company decide what ads to display with each query so as to maximize its revenue? 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. |
| Authors: | Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh |
| Contact email: | saberi@stanford.edu |
| | Number of views : 1117 Number of downloads : 708 |
