1;3409;0c AdWords and generalized online matching

AdWords and generalized online matching

Journal of the ACM, vol. 54, no. 5, 2007
DOI: 10.1145/1284320.1284321

JACM

bibtex

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 trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1−1/e for this problem.