AdWords and generalized Online matching

被引：319
作者：
Mehta, Aranyak
Saberi, Amin
Vazirani, Umesh
Vazirani, Vijay
机构：
[1] Google Inc, Mountain View, CA 94043 USA
[2] Stanford Univ, Inst Computat & Math Engn, Dept Management Sci & Engn, Stanford, CA USA
[3] Univ Calif Berkeley, Dept Comp Sci, Berkeley, CA USA
[4] Georgia Inst Technol, Coll Comp, Atlanta, GA 30332 USA
来源：
JOURNAL OF THE ACM | 2007年 / 54卷 / 05期
关键词：
algorithms; economics; theory; keyword auctions; search engines; online algorithms;
D O I：
10.1145/1284320.1284321
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
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 trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1 - 1/e for this problem.
引用
收藏
页数：19
相关论文
共 30 条
[1]  
AGGARWAL G, 2006, P ACM C EL COMM EC
[2]   On-line routing of virtual circuits with applications to load balancing and machine scheduling [J].
Aspnes, J ;
Azar, Y ;
Fiat, A ;
Plotkin, S ;
Waarts, O .
JOURNAL OF THE ACM, 1997, 44 (03) :486-504
[3]   Maximizing throughput in multi-queue switches [J].
Azar, Y ;
Litichevskey, A .
ALGORITHMICA, 2006, 45 (01) :69-90
[4]   Cell breathing in wireless LANs: Algorithms and evaluation [J].
Bahl, Paramvir ;
Hajiaghayi, Mohammad T. ;
Jain, Kamal ;
Mirrokni, Sayyed Vahab ;
Qiu, Lili ;
Saberi, Amin .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2007, 6 (02) :164-178
[5]  
Bansal N, 2004, LECT NOTES COMPUT SC, V3142, P196
[6]  
Battelle J., 2005, The Search: How Google and Its Rivals Rewrote the Rules of Business and Transformed Our Culture
[7]  
BORGS C, 2007, P ACM C EL COMM ACM
[8]  
BUCHBINDER N, 2007, IN PRESS P 15 ANN EU
[9]   JOB MATCHING WITH HETEROGENEOUS FIRMS AND WORKERS [J].
CRAWFORD, VP ;
KNOER, EM .
ECONOMETRICA, 1981, 49 (02) :437-450
[10]   MULTIITEM AUCTIONS [J].
DEMANGE, G ;
GALE, D ;
SOTOMAYOR, M .
JOURNAL OF POLITICAL ECONOMY, 1986, 94 (04) :863-872
123