AdWords and Generalized On-line Matching
Authors:
- 15 November 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 264-273
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
This publication has 14 references indexed in Scilit:
- Maximizing Throughput in Multi-queue SwitchesLecture Notes in Computer Science, 2004
- Auctions with Budget ConstraintsLecture Notes in Computer Science, 2004
- A new greedy approach for facility location problems2002
- Combinatorial auctions with decreasing marginal utilities2001
- An optimal deterministic algorithm for online b-matchingTheoretical Computer Science, 2000
- An improved approximation ratio for the minimum latency problemMathematical Programming, 1998
- On-line network optimization problems1998
- An optimal algorithm for on-line bipartite matching1990
- Probabilistic computations: Toward a unified measure of complexity1977
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesIEEE Transactions on Information Theory, 1977