How does a search engine company decide what ads to display with each query so as to maximize its revenueq This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1−1/ e  for this problem.
['Aranyak Mehta', 'Amin Saberi', 'Umesh V. Vazirani', 'Vijay V. Vazirani']
AdWords and generalized online matching