2007/10/01 by Aranyak Mehta, Amin Saberi, Umesh Vazirani +1 · 3 citations
Computer Science · Decision Sciences · Engineering · #Optimization and Search Problems #Auction Theory and Applications #Vehicle Routing Optimization Methods
paper · doi:10.1145/1284320.1284321
openalex publication_date 2007/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.