Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue

By Niv Buchbinder, Kamal Kumar Jain, Joseph (Seffi) Naor. Embedded Systems and Applications, 2007

379 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/bf8350ab0e43ffd893a3e9f27d3428a90deb8915

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 Management Science and Operations Research

Citations in the corpus

Online Matching and Ad Allocation (2013, methodology): “[21] studied the Adwords problem with the small bids assumption using the Primal–Dual approach.”
Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs (2011, background): “The online version of this problem also has many applications, from matching patients and donated organs to allocating online advertisement space [9, 15, 4, 11].”
Online Task Assignment in Crowdsourcing Markets (2012, background): “…build on the online primal-dual framework, which has been used to analyze a variety of online optimization problems, including online network optimization (Alon et al. 2004), online paging (Bansal, Buchbinder, and Naor 2007), and the online adwords problem (Buchbinder, Jain, and Naor 2007).”
The adwords problem: online keyword matching with budgeted bidders under random permutations (2009, methodology): “Buchbinder, Jain and Naor [5] also gave a 1 − 1 /e competitive algorithm for the adwords problem using a primal-dual framework.”
Online Stochastic Matching: Beating 1-1/e (2009, background): “For the online setting, it is typically a ssumed that every weight is very small compared to the corresponding budget, in which case there exist 1 − 1/e factor online algorithms [16, 6, 12, 1].”
A Dynamic Near-Optimal Algorithm for Online Linear Programming (2009, background): “There were several previous studies on this problem under the worst case input model [23, 7, 16], for which an 1 − 1/e competitive algorithm exists, and this factor is tight.”
The Design of Competitive Online Algorithms via a Primal-Dual Approach (2009, methodology): “[30] who showed how to obtain a randomized e/(e − 1)competitive algorithm via the primal–dual approach.”