{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T18:14:37Z","timestamp":1769278477411,"version":"3.49.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,2,8]],"date-time":"2012-02-08T00:00:00Z","timestamp":1328659200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s00453-012-9614-x","type":"journal-article","created":{"date-parts":[[2012,2,7]],"date-time":"2012-02-07T16:39:12Z","timestamp":1328632752000},"page":"634-661","source":"Crossref","is-referenced-by-count":10,"title":["Stochastic Budget Optimization in Internet Advertising"],"prefix":"10.1007","volume":"65","author":[{"given":"Bhaskar","family":"DasGupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,8]]},"reference":[{"key":"9614_CR1","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1137\/S0097539704441629","volume":"35","author":"N. Alon","year":"2006","unstructured":"Alon, N., Naor, A.: Approximating the cut-norm via Grothendieck\u2019s inequality. SIAM J. Comput. 35, 787\u2013803 (2006)","journal-title":"SIAM J. Comput."},{"key":"9614_CR2","first-page":"1","volume-title":"7th ACM Conference on Electronic Commerce","author":"G. Aggarwal","year":"2006","unstructured":"Aggarwal, G., Goel, A., Motwani, R.: Truthful auctions for pricing search keywords. In: 7th ACM Conference on Electronic Commerce, pp. 1\u20137 (2006)"},{"key":"9614_CR3","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results, further improvements. Electronic Colloquium on Computational Complexity 5(29) (1998)"},{"key":"9614_CR4","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1145\/1242572.1242644","volume-title":"16th International World Wide Web Conference","author":"C. Borgs","year":"2007","unstructured":"Borgs, C., Chayes, J., Etesami, O., Immorlica, N., Jain, K., Mahdian, M.: Dynamics of bid optimization in online advertisement auctions. In: 16th International World Wide Web Conference, pp. 531\u2013540 (2007)"},{"issue":"2","key":"9614_CR5","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.ipl.2007.07.005","volume":"105","author":"T.-M. Bu","year":"2008","unstructured":"Bu, T.-M., Deng, X., Qi, Q.: Forward looking Nash equilibrium for keyword auction. Inf. Process. Lett. 105(2), 41\u201346 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9614_CR6","first-page":"262","volume-title":"8th ACM Conference on Electronic Commerce","author":"M. Cary","year":"2007","unstructured":"Cary, M., Das, A., Edelman, B., Giotis, I., Heimerl, K., Karlin, A.R., Mathieu, C., Schwarz, M.: Greedy bidding strategies for keyword auctions. In: 8th ACM Conference on Electronic Commerce, pp. 262\u2013271 (2007)"},{"issue":"3","key":"9614_CR7","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C. Chekuri","year":"2006","unstructured":"Chekuri, C., Khanna, S.: A PTAS for the multiple knapsack problem. SIAM J. Comput. 35(3), 713\u2013728 (2006)","journal-title":"SIAM J. Comput."},{"key":"9614_CR8","doi-asserted-by":"crossref","unstructured":"Cocco, F., Consiglio, A., Zenios, S.: Scenario Optimization asset and liability modeling for endowments with guarantees, Wharton Financial Institutions Center WP No. 00-41, June 12 (2000). Available at http:\/\/ssrn.com\/abstract=253039 or doi: 10.2139\/ssrn.253039","DOI":"10.2139\/ssrn.253039"},{"issue":"1","key":"9614_CR9","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF02204809","volume":"30","author":"R.S. Dembo","year":"1991","unstructured":"Dembo, R.S.: Scenario optimization. Ann. Oper. Res. 30(1), 63\u201380 (1991)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"9614_CR10","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1257\/aer.97.1.242","volume":"97","author":"B. Edelman","year":"2007","unstructured":"Edelman, B., Ostrovsky, M., Schwarz, M.: Internet advertising and the generalized second price auction: selling billions of dollars worth of keywords. Am. Econ. Rev. 97(1), 242\u2013259 (2007)","journal-title":"Am. Econ. Rev."},{"key":"9614_CR11","first-page":"40","volume-title":"8th ACM Conference on Electronic Commerce","author":"J. Feldman","year":"2007","unstructured":"Feldman, J., Muthukrishnan, S., P\u00e1l, M., Stein, C.: Budget optimization in search-based advertising auctions. In: 8th ACM Conference on Electronic Commerce, 40\u201349 (2007)"},{"key":"9614_CR12","volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9614_CR13","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"9614_CR14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2212\u03b5 . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"2","key":"9614_CR15","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1108\/eb043460","volume":"2","author":"H. Mausser","year":"2001","unstructured":"Mausser, H., Rosen, D.: Applying scenario optimization to portfolio credit risk. J. Risk Finance 2(2), 36\u201348 (2001)","journal-title":"J. Risk Finance"},{"issue":"4","key":"9614_CR16","doi-asserted-by":"crossref","first-page":"1392","DOI":"10.1137\/080731207","volume":"39","author":"K. Jansen","year":"2009","unstructured":"Jansen, K.: Parameterized approximation scheme for the multiple knapsack problem. SIAM J. Comput. 39(4), 1392\u20131412 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9614_CR17","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"E.L. Lawler","year":"1979","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4), 339\u2013356 (1979)","journal-title":"Math. Oper. Res."},{"key":"9614_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"issue":"4","key":"9614_CR19","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1007\/s00453-009-9311-6","volume":"58","author":"S. Muthukrishnan","year":"2010","unstructured":"Muthukrishnan, S., P\u00e1l, M., Svitkina, Z.: Stochastic models for budget optimization in search-based advertising. Algorithmica 58(4), 1022\u20131044 (2010)","journal-title":"Algorithmica"},{"issue":"6","key":"9614_CR20","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1016\/j.ijindorg.2006.10.002","volume":"25","author":"H. Varian","year":"2007","unstructured":"Varian, H.: Position auctions. Int. J. Ind. Organ. 25(6), 1163\u20131178 (2007)","journal-title":"Int. J. Ind. Organ."},{"key":"9614_CR21","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"9614_CR22","volume-title":"Financial Optimization","year":"1996","unstructured":"Zenios, S.A. (ed.): Financial Optimization. Cambridge University Press, Cambridge (1996)"},{"key":"9614_CR23","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1007\/978-3-540-92185-1_63","volume-title":"4th International Workshop on Internet and Network Economics","author":"Y. Zhou","year":"2008","unstructured":"Zhou, Y., Chakrabarty, D., Lukose, R.: Budget constrained bidding in keyword auctions and online knapsack problems. In: 4th International Workshop on Internet and Network Economics, pp. 566\u2013576 (2008)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9614-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9614-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9614-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:09Z","timestamp":1559137509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9614-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,8]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["9614"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9614-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,8]]}}}