loading...
AdWords and Generalized On-line Matching
Pittsburgh, Pennsylvania, USA October 23-October 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.1246th Annual IEEE Symposium on Foundat ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani, "AdWords and Generalized On-line Matching," Foundations of Computer Science, Annual IEEE Symposium on, pp. 264-273, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2005.12,
author = {Aranyak Mehta and Amin Saberi and Umesh Vazirani and Vijay Vazirani},
title = {AdWords and Generalized On-line Matching},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2005},
isbn = {0-7695-2468-0},
pages = {264-273},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.12},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - AdWords and Generalized On-line Matching
SN - 0-7695-2468-0
SP264
EP273
A1 - Aranyak Mehta,
A1 - Amin Saberi,
A1 - Umesh Vazirani,
A1 - Vijay Vazirani,
PY - 2005
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Aranyak Mehta, Aranyak Mehta
Amin Saberi, Amin Saberi
Umesh Vazirani, Umesh Vazirani
Vijay Vazirani, Vijay Vazirani

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.

Citation:
Aranyak Mehta, Amin Saberi, Umesh Vazirani, Vijay Vazirani, "AdWords and Generalized On-line Matching," focs, pp.264-273, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.