{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T03:43:01Z","timestamp":1783136581132,"version":"3.54.6"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T00:00:00Z","timestamp":1191196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2007,10]]},"abstract":"<jats:p>\n            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\u22121\/\n            <jats:italic>e<\/jats:italic>\n            for this problem.\n          <\/jats:p>","DOI":"10.1145\/1284320.1284321","type":"journal-article","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T16:11:36Z","timestamp":1192810296000},"page":"22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":375,"title":["AdWords and generalized online matching"],"prefix":"10.1145","volume":"54","author":[{"given":"Aranyak","family":"Mehta","sequence":"first","affiliation":[{"name":"Google, Inc., Mountain View, California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amin","family":"Saberi","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Umesh","family":"Vazirani","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijay","family":"Vazirani","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, Georgia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134708"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258201"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1190-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2007.20"},{"key":"e_1_2_1_5_1","volume-title":"ICALP. LNCS","volume":"3142","author":"Bansal N.","unstructured":"Bansal , N. , Fleischer , L. , Kimbrel , T. , Mahdian , M. , Schieber , B. , and Sviridenko , M . 2004. Further improvements in competitive guarantees for QoS buffering . In ICALP. LNCS , vol. 3142 . Springer, 196--207. Bansal, N., Fleischer, L., Kimbrel, T., Mahdian, M., Schieber, B., and Sviridenko, M. 2004. Further improvements in competitive guarantees for QoS buffering. In ICALP. LNCS, vol. 3142. Springer, 196--207."},{"key":"e_1_2_1_6_1","volume-title":"The Search: How Google and Its Rivals Rewrote the Rules of Business and Transformed Our Culture. Portfolio Trade.","author":"Battelle J.","year":"2005","unstructured":"Battelle , J. 2005 . The Search: How Google and Its Rivals Rewrote the Rules of Business and Transformed Our Culture. Portfolio Trade. Battelle, J. 2005. The Search: How Google and Its Rivals Rewrote the Rules of Business and Transformed Our Culture. Portfolio Trade."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064014"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 15th Annual European Symposium on Algorithms","author":"Buchbinder N.","unstructured":"Buchbinder , N. , Jain , K. , and Naor , J. S . 2007. Online primal-dual algorithms for maximizing ad auctions revenue . In Proceedings of the 15th Annual European Symposium on Algorithms ( Eilat, Israel, Oct. 8--10). To appear. Buchbinder, N., Jain, K., and Naor, J. S. 2007. Online primal-dual algorithms for maximizing ad auctions revenue. In Proceedings of the 15th Annual European Symposium on Algorithms (Eilat, Israel, Oct. 8--10). To appear."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913320"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1086\/261411"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Edelman B. Ostrovsky M. and Schwarz M. 2005. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. NBER working paper 11765.  Edelman B. Ostrovsky M. and Schwarz M. 2005. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. NBER working paper 11765.","DOI":"10.3386\/w11765"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08)","author":"Goel G.","unstructured":"Goel , G. , and Mehta , A . 2008. Online assignment in a distributional model with applications to Adwords allocations . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08) . To appear. Goel, G., and Mehta, A. 2008. Online assignment in a distributional model with applications to Adwords allocations. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'08). To appear."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585867"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 3rd Workshop on Sponsored Search Auctions.","author":"Gonen R.","unstructured":"Gonen , R. , and Pavlov , E . 2007. An incentive-compatible multi-armed bandit mechanism . In Proceedings of the 3rd Workshop on Sponsored Search Auctions. Gonen, R., and Pavlov, E. 2007. An incentive-compatible multi-armed bandit mechanism. In Proceedings of the 3rd Workshop on Sponsored Search Auctions."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11600930_5"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2nd Workshop on Sponsored Search Auctions.","author":"Iyengar G.","unstructured":"Iyengar , G. , and Kumar , A . 2006. Optimal keyword auctions . In Proceedings of the 2nd Workshop on Sponsored Search Auctions. Iyengar, G., and Kumar, A. 2006. Optimal keyword auctions. In Proceedings of the 2nd Workshop on Sponsored Search Auctions."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram B. and Pruhs K. 1998. On-line network optimization problems. In Developments from a June 1996 Seminar on Online Algorithms. Springer-Verlag New York 268--280.   Kalyanasundaram B. and Pruhs K. 1998. On-line network optimization problems. In Developments from a June 1996 Seminar on Online Algorithms. Springer-Verlag New York 268--280.","DOI":"10.1007\/BFb0029573"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Lahaie S. Pennock D. Saberi A. and Vohra R. 2007. Sponsored Search. In N. Nisan T. Roughgarden E. Tardos V.V. Vazirani Eds Algorithmic Game Theory Cambridge University Press Cambridge UK.  Lahaie S. Pennock D. Saberi A. and Vohra R. 2007. Sponsored Search. In N. Nisan T. Roughgarden E. Tardos V.V. Vazirani Eds Algorithmic Game Theory Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511800481.030"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501161"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Mahdian M. Markakis E. Saberi A. and \n      Vazirani V\n  . \n  2001\n  . A greedy facility location algorithm analyzed using dual fitting. In RANDOM-APPROX Lecture Notes in Computer Science vol. \n  2129\n  . \n  Springer New York.   Mahdian M. Markakis E. Saberi A. and Vazirani V. 2001. A greedy facility location algorithm analyzed using dual fitting. In RANDOM-APPROX Lecture Notes in Computer Science vol. 2129. Springer New York.","DOI":"10.1007\/3-540-44666-4_16"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250952"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055688"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.12"},{"key":"e_1_2_1_28_1","unstructured":"Varian H. R. 2006. Position auctions. Int. J. Indust. Org. To appear.  Varian H. R. 2006. Position auctions. Int. J. Indust. Org. To appear."},{"key":"e_1_2_1_29_1","unstructured":"Vazirani V. V. 2006. Spending constraint utilities with applications to the AdWords market. Math. Oper. Res. (submitted). Available at http:\/\/www.cc.gatech.edu\/vijay.vazirani\/spending.pdf.  Vazirani V. V. 2006. Spending constraint utilities with applications to the AdWords market. Math. Oper. Res. (submitted). Available at http:\/\/www.cc.gatech.edu\/vijay.vazirani\/spending.pdf."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1284320.1284321","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1284320.1284321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:01Z","timestamp":1750259641000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1284320.1284321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1145\/1284320.1284321"],"URL":"https:\/\/doi.org\/10.1145\/1284320.1284321","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10]]},"assertion":[{"value":"2007-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}