AdWords and Generalized On-line Matching

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Aranyak Mehta Articles by Amin Saberi Articles by Umesh Vazirani Articles by Vijay Vazirani

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)

Pittsburgh, Pennsylvania, USA

October 23-October 25

ISBN: 0-7695-2468-0

	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

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.12

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.