AdWords and generalized on-line matching

By Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani. IEEE Annual Symposium on Foundations of Computer Science, 2005

944 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Industrial and Manufacturing Engineering, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/6fd59986eec1be8bc5544ed6f8d1c60fb8242b64

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

In Management Science and Operations Research

Citations in the corpus

The Design of Competitive Online Algorithms via a Primal-Dual Approach (2009, background): “[82] builds on previous work on online bipartite matching [73] and online b-matching [69].”
The adwords problem: online keyword matching with budgeted bidders under random permutations (2009, methodology): “Some of the features that have been considered (or ignored) in the models [20, 8, 19, 16, 18, 4, 7, 17, 1, 9] include: online vs. oﬄine or equilibrium properties, algorithm design vs mechanism design, single keyword vs multiple keywords, incorporating budgets or not, and pay per click vs pay per…”
Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs (2011, methodology): “If LPs in such a family have a nice form, we can solve each of them analytically and get a tight bound on the ratio of the algorithm (as was done in [15, 11]).”
A Dynamic Near-Optimal Algorithm for Online Linear Programming (2009, neutral): “G T ] 1 6 N ov 2 00”
Streaming graph partitioning for large distributed graphs (2012, methodology): “[27] on an algorithm for AdWords.”
Online mobile Micro-Task Allocation in spatial crowdsourcing (2016, background): “In addition, a close branch of research is the online maximum weighted bipartite matching (OMWBM) problem [9], [10], [11], where the information of the left-hand vertices in a bipartite graph is known, and the right-hand vertices arrive dynamically.”
An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs (2006, methodology): “This technique was used in [7, 14, 15] before it was explicitly named and used in [11, 12, 16].”
Secretary Problems via Linear Programming (2010, methodology): “Our linear programming technique is similar to the technique of factor revealing linear programs that have been used successfully in many different settings [7, 12, 14, 19].”
Online Matching and Ad Allocation (2013, methodology): “The Adwords problem with the small bids assumption can be solved with a (1 − 4) approximation if the bid to budget ratio is at most [23].”
There’s plenty of room at the Top: What will drive computer performance after Moore’s law? (2020, methodology): “Google ’ s PageRank algorithm ( 18 ) made its World Wide Web search superior, and the auction algorithms of Google AdWords ( 19 ), which allow advertisers to bid for display space based on users ’ search terms, made it highly profitable.”
Optimal real-time bidding for display advertising (2014, background): “Nonetheless, most research has been so far limited to keyword auction in the context of sponsored search (SS) [15, 4, 28].”
Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue (2007, methodology): “The(1−1/e) competitive factor is tight for the general ad-auctions model considered by [15].”