{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T15:09:39Z","timestamp":1769267379790,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,5,7]],"date-time":"2009-05-07T00:00:00Z","timestamp":1241654400000},"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":[[2010,12]]},"DOI":"10.1007\/s00453-009-9311-6","type":"journal-article","created":{"date-parts":[[2009,5,6]],"date-time":"2009-05-06T15:56:15Z","timestamp":1241625375000},"page":"1022-1044","source":"Crossref","is-referenced-by-count":30,"title":["Stochastic Models for Budget Optimization in\u00a0Search-Based Advertising"],"prefix":"10.1007","volume":"58","author":[{"given":"S.","family":"Muthukrishnan","sequence":"first","affiliation":[]},{"given":"Martin","family":"P\u00e1l","sequence":"additional","affiliation":[]},{"given":"Zoya","family":"Svitkina","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,7]]},"reference":[{"issue":"2","key":"9311_CR1","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1137\/S1052623499363220","volume":"12","author":"A.J. Kleywegt","year":"2002","unstructured":"Kleywegt, A.J., Shapiro, A., Homem-de-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2), 479\u2013502 (2002)","journal-title":"SIAM J. Optim."},{"key":"9311_CR2","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Pal, M.: Sampling bounds for stochastic optimization. In: Proc. 9th International Workshop on Randomization and Computation (2005)","DOI":"10.1007\/11538462_22"},{"issue":"1","key":"9311_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1122480.1122493","volume":"37","author":"C. Swamy","year":"2006","unstructured":"Swamy, C., Shmoys, D.B.: Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1), 33\u201346 (2006)","journal-title":"SIGACT News"},{"key":"9311_CR4","doi-asserted-by":"crossref","unstructured":"Feldman, J., Muthukrishnan, S., Pal, M., Stein, C.: Budget optimization in search-based advertising auctions. In: Proc. 9th ACM Conf. on Electronic Commerce (2007)","DOI":"10.1145\/1250910.1250917"},{"key":"9311_CR5","doi-asserted-by":"crossref","unstructured":"Dean, B.C., Goemans, M.X., Vondrak, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. In: Proc. 45th IEEE Symp. on Foundations of Computer Science, pp.\u00a0208\u2013217 (2004)","DOI":"10.1109\/FOCS.2004.15"},{"issue":"1","key":"9311_CR6","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1137\/S0097539797329142","volume":"30","author":"J. Kleinberg","year":"2000","unstructured":"Kleinberg, J., Rabani, Y., Tardos, E.: Allocating bandwidth for bursty connections. SIAM J. Comput. 30(1), 191\u2013217 (2000)","journal-title":"SIAM J. Comput."},{"key":"9311_CR7","doi-asserted-by":"crossref","unstructured":"Goel, A., Indyk, P.: Stochastic load balancing and related problems. In: Proc. 40th IEEE Symp. on Foundations of Computer Science (1999)","DOI":"10.1109\/SFFCS.1999.814632"},{"key":"9311_CR8","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/nav.3220400203","volume":"40","author":"R.L. Carraway","year":"1993","unstructured":"Carraway, R.L., Schmidt, R.L., Weatherford, L.R.: An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns. Nav. Res. Logist. 40, 161\u2013173 (1993)","journal-title":"Nav. Res. Logist."},{"issue":"5","key":"9311_CR9","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1287\/opre.38.5.820","volume":"38","author":"M.I. Henig","year":"1990","unstructured":"Henig, M.I.: Risk criteria in a stochastic knapsack problem. Oper. Res. 38(5), 820\u2013825 (1990)","journal-title":"Oper. Res."},{"issue":"11","key":"9311_CR10","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1057\/jors.1980.189","volume":"31","author":"M. Sniedovich","year":"1980","unstructured":"Sniedovich, M.: Preference order stochastic knapsack problems: methodological issues. J. Oper. Res. Soc. 31(11), 1025\u20131032 (1980)","journal-title":"J. Oper. Res. Soc."},{"issue":"2","key":"9311_CR11","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1057\/jors.1979.27","volume":"30","author":"E. Steinberg","year":"1979","unstructured":"Steinberg, E., Parks, M.: A preference order dynamic program for a knapsack problem with stochastic rewards. J. Oper. Res. Soc. 30(2), 141\u2013147 (1979)","journal-title":"J. Oper. Res. Soc."},{"key":"9311_CR12","unstructured":"Chakrabarty, D., Zhou, Y., Lukose, R.: Budget constrained bidding in keyword auctions and online knapsack problems. In: WWW2007 Workshop on Sponsored Search Auctions (2007)"},{"key":"9311_CR13","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Proc. 10th APPROX (2007)","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"9311_CR14","doi-asserted-by":"crossref","unstructured":"Rusmevichientong, P., Williamson, D.P.: An adaptive algorithm for selecting profitable keywords for search-based advertising services. In: Proc. 8th ACM Conf. on Electronic Commerce, pp.\u00a0260\u2013269 (2006)","DOI":"10.1145\/1134707.1134736"},{"key":"9311_CR15","doi-asserted-by":"crossref","unstructured":"Ostrovsky, M., Edelman, B., Schwarz, M.: Internet advertising and the generalized second price auction: selling billions of dollars worth of keywords. Am. Econ. Rev. 97(1) (2007)","DOI":"10.1257\/000282807780323523"},{"key":"9311_CR16","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, A., Motwani, R.: Truthful auctions for pricing search keywords. In: Proc. 8th ACM Conf. on Electronic Commerce, pp. 1\u20137 (2006)","DOI":"10.1145\/1134707.1134708"},{"key":"9311_CR17","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: Proc. 7th ACM Conf. on Electronic Commerce, pp.\u00a044\u201351 (2005)","DOI":"10.1145\/1064009.1064014"},{"key":"9311_CR18","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J., Etesami, O., Immorlica, N., Jain, K., Mahdian, M.: Bid optimization in online advertisement auctions. In: 16th International World Wide Web Conference (2007)","DOI":"10.1145\/1242572.1242644"},{"key":"9311_CR19","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. J. ACM 54(5) (2007)","DOI":"10.1145\/1284320.1284321"},{"key":"9311_CR20","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Nazerzadeh, H., Saberi, A.: Allocating online advertisement space with unreliable estimates. In: Proc. 9th ACM Conf. on Electronic Commerce (2007)","DOI":"10.1145\/1250910.1250952"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9311-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9311-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9311-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:04Z","timestamp":1559137504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9311-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,7]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["9311"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9311-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,7]]}}}