AdWords and generalized online matching
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani · Journal of the ACM · 2007
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.