AdWords and Generalized On-line Matching
Published 15 November 2005
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay V. Vazirani
Citations266
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
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 tradeoff revealing LP and use it to derive two optimal algorithms achieving competitive ratios of 1-1/e for this problem.
Keywords
Computer ScienceDecision SciencesEngineering
An optimal algorithm for on-line bipartite matching
701 Citations1990Richard M. Karp, Umesh Vazirani +1 more
This work applies the general approach to data structures, bin packing, graph coloring, and graph coloring to bipartite matching and shows that a simple randomized on-line algorithm achieves the best possible performance.
Journal of Political EconomyMulti-Item Auctions
608 Citations1986Gabrielle Demange, David Gale +1 more
Journal of the ACMGreedy facility location algorithms analyzed using dual fitting with factor-revealing LP
493 Citations2003Kamal Jain, Mohammad Mahdian +3 more
The method of dual fitting and the idea of factor-revealing LP are formalized and used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem.
Games and Economic BehaviorCombinatorial auctions with decreasing marginal utilities
473 Citations2005Benny Lehmann, Daniel Lehmann +1 more
IEEE Transactions on Information TheoryNew upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
447 Citations1977Robert J. McEliece, E. R. Rodemich +2 more
With the Delsarte-MacWilliams inequalities as a starting point, an upper bound is obtained on the rate of a binary code as a function of its minimum distance, which is asymptotically less than Levenshtein's bound and so also Elias's.
A new greedy approach for facility location problems
403 Citations2002Kamal Jain, Mohammad Mahdian +1 more
A simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61 and proving a lower bound of 1+2/e on the approximability of the k-median problem.
Game theory, on-line prediction and boosting
386 Citations1996Yoav Freund, Robert E. Schapire
An algorithm for learning to play repeated games based on the on-line prediction methods of Littlestone and Warmuth is described, which yields a simple proof of von Neumann’s famous minmax theorem, as well as a provable method of approximately solving a game.
Journal of the ACMOn-line routing of virtual circuits with applications to load balancing and machine scheduling
333 Citations1997James Aspnes, Yossi Azar +3 more
An algorithm is described that achieves on-line allocation of routes to virtual circuits (both point-to-point and multicast) with a constant competitive ratio with respect to maximum congestin, where n is the number of nodes in the network.
Truthful auctions for pricing search keywords
329 Citations2006Gagan Aggarwal, Ashish Goel +1 more
This work presents a truthful auction for pricing advertising slots on a web-page assuming that advertisements for different merchants must be ranked in decreasing order of their (weighted) bids.
Combinatorial auctions with decreasing marginal utilities
234 Citations2001Benny Lehmann, Daniel Lehmann +1 more
While it is shown that the allocation problem among valuations with decreasing marginal utilities is NP-hard, an efficient greedy 2-approximation algorithm is presented for this case because no such approximation algorithm exists in a setting allowing for complementarities.
Multi-unit auctions with budget-constrained bidders
228 Citations2005Christian Borgs, Jennifer Chayes +3 more
It is proved that it is impossible to design a non-trivial truthful auction which allocates all units, while the design of an asymptotically revenue-maximizing truthful mechanism which may allocate only some of the units is provided.
Theoretical Computer ScienceAn optimal deterministic algorithm for online b-matching
199 Citations2000Bala Kalyanasundaram, Kirk Pruhs
Mathematical ProgrammingAn improved approximation ratio for the minimum latency problem
131 Citations1998Michel X. Goemans, Jon Kleinberg
The development of the algorithm involves a number of techniques that seem to be of interest from the perspective of the TSP and its variants more generally, and improves the approximation ratio to 21.55.
Allocating online advertisement space with unreliable estimates
130 Citations2007Mohammad Mahdian, Hamid Nazerzadeh +1 more
The problem of optimally allocating online advertisement space to budget-constrained advertisers is studied and an algorithm that takes advantage of the given estimates of the frequencies of keywords to compute a near optimal solution when the estimates are accurate, while at the same time maintaining a good worst-case competitive ratio.
IEEE Transactions on Mobile ComputingCell Breathing in Wireless LANs: Algorithms and Evaluation
127 Citations2007Paramvir Bahl, Mohammad Taghi Hajiaghayi +4 more
This work proposes cell breathing, a well-known concept in cellular telephony, as a load balancing mechanism to handle client congestion in a wireless LAN, and develops power management algorithms for controlling the coverage of access points to handle dynamic changes in client workloads.
Lecture notes in computer scienceClick Fraud Resistant Methods for Learning Click-Through Rates
123 Citations2005Nicole Immorlica, Kamal Jain +2 more
It is demonstrated that a particular class of learning algorithms, called click-based algorithms, are resistant to click fraud in some sense, and it is shown that other common learning algorithms are vulnerable to fraudulent attacks.
Lecture notes in computer scienceAuctions with Budget Constraints
81 Citations2004Nir Andelman, Yishay Mansour
This paper presents exact and approximate algorithms for auctions with budget constraints, and presents a randomized algorithm with an approximation ratio of \(\frac{e}{e-1}\cong\) 1.582, which can be derandomized.
AlgorithmicaMaximizing throughput in multi-queue switches
69 Citations2006Yossi Azar, Arik Litichevskey
The main result in this paper shows that forB which is not too small the algorithm can do better than 1.89, and approach a competitive ratio ofe/(e − 1) ≈ 1.58.
Lecture notes in computer scienceA Greedy Facility Location Algorithm Analyzed Using Dual Fitting
69 Citations2001Mohammad Mahdian, Evangelos Markakis +2 more
A natural greedyalgorithm for the metric uncapacitated facilitylo cation problem is presented and the method of dual fitting is used to analyze its approximation ratio, which turns out to be 1.861.
Mathematics of Operations ResearchSpending Constraint Utilities with Applications to the Adwords Market
65 Citations2010Vijay V. Vazirani
A new, natural class of utility functions that allow buyers to explicitly provide information on their relative preferences as a function of the amount of money spent on each good are presented.
Lecture notes in computer scienceFurther Improvements in Competitive Guarantees for QoS Buffering
60 Citations2004Nikhil Bansal, Lisa Fleischer +4 more
A modification of the previously proposed “preemptive greedy” algorithm of for buffer management is described and an analysis is given to show that this algorithm achieves a competitive ratio of at most 1.75.
Lecture notes in computer scienceMaximizing Throughput in Multi-queue Switches
24 Citations2004Yossi Azar, Arik Litichevskey