{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T03:42:59Z","timestamp":1783136579147,"version":"3.54.6"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642108402","type":"print"},{"value":"9783642108419","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10841-9_34","type":"book-chapter","created":{"date-parts":[[2009,12,8]],"date-time":"2009-12-08T17:14:44Z","timestamp":1260292484000},"page":"374-385","source":"Crossref","is-referenced-by-count":110,"title":["Online Ad Assignment with Free Disposal"],"prefix":"10.1007","author":[{"given":"Jon","family":"Feldman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nitish","family":"Korula","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"P\u00e1l","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"34_CR1","unstructured":"Alaei, S., Malekian, A.: Maximizing sequence-submodular functions (2009) (manuscript)"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Azar, Y., Birnbaum, B., Karlin, A.R., Mathieu, C., Nguyen, C.T.: Improved Approximation Algorithms for Budgeted Allocations. In: Proc. Automata, Languages and Programming (2008)","DOI":"10.1007\/978-3-540-70575-8_16"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Hartline, J., Kleinberg, R.: Selling ad campaigns: Online algorithms with cancellations. In: ACM EC (2009)","DOI":"10.1145\/1566374.1566383"},{"key":"34_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-75520-3_24","volume-title":"Algorithms \u2013 ESA 2007","author":"N. Buchbinder","year":"2007","unstructured":"Buchbinder, N., Jain, K., Naor, J.S.: Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 253\u2013264. Springer, Heidelberg (2007)"},{"issue":"2-3","key":"34_CR5","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N. Buchbinder","year":"2007","unstructured":"Buchbinder, N., Naor, J.: The Design of Competitive Online Algorithms via a Primal-Dual Approach. Foundations and Trends in Theoretical Computer Science\u00a03(2-3), 93\u2013263 (2007)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Goel, G.: On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. In: Proc. FOCS, pp. 687\u2013696 (2008)","DOI":"10.1109\/FOCS.2008.47"},{"key":"34_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1007\/978-3-642-03685-9_4","volume-title":"APPROX and RANDOM 2009","author":"C. Chekuri","year":"2009","unstructured":"Chekuri, C., Ene, A., Korula, N.: Unsplittable flow in paths and trees and column-restricted packing integer programs. In: Dinur, I., et al. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 42\u201355. Springer, Heidelberg (2009)"},{"key":"34_CR8","unstructured":"Chekuri, C., Khanna, S.: A PTAS for the multiple knapsack problem. In: 11th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 213\u2013222 (2000)"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"Devanur, N., Hayes, T.: The adwords problem: Online keyword matching with budgeted bidders under random permutations. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 71\u201378 (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U., Immorlica, N., Mirrokni, V., Nazerzadeh, H.: A combinatorial allocation mechanism for banner advertisement with penalties. In: WWW (2008)","DOI":"10.1145\/1367497.1367521"},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondrak, J.: Approximation algorithms for allocation problems: Improving the factor of 1-1\/e. In: FOCS (2006)","DOI":"10.1109\/FOCS.2006.14"},{"key":"34_CR12","unstructured":"Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: Beating 1 - 1\/e. In: FOCS (to appear, 2009)"},{"key":"34_CR13","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"M. Fisher","year":"1978","unstructured":"Fisher, M., Nemhauser, G., Wolsey, L.: An analysis of the approximations for maximizing submodular set functions II. Math. Prog. St.\u00a08, 73\u201387 (1978)","journal-title":"Math. Prog. St."},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Goemans, M., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: Proc. SODA (2006)","DOI":"10.1145\/1109557.1109624"},{"key":"34_CR15","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: SODA, pp. 982\u2013991 (2008)"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for online bipartite matching. In: Proc. STOC (1990)","DOI":"10.1145\/100216.100262"},{"key":"34_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1007\/978-3-642-02930-1_42","volume-title":"ICALP 2009, Part II","author":"N. Korula","year":"2009","unstructured":"Korula, N., Pal, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Albers, S., et al. (eds.) ICALP 2009, Part II. LNCS, vol.\u00a05556, pp. 508\u2013520. Springer, Heidelberg (2009)"},{"key":"34_CR18","doi-asserted-by":"crossref","unstructured":"Lehman, Lehman, Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games and Economic Behaviour, 270\u2013296 (2006)","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"34_CR19","unstructured":"Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. In: FOCS (2005)"},{"key":"34_CR20","doi-asserted-by":"crossref","unstructured":"Pritchard, D.: Approximability of Sparse Integer Programs. In: Proceedings of the 17th Annual European Symposium on Algorithms, pp. 83\u201394 (2009)","DOI":"10.1007\/978-3-642-04128-0_8"},{"issue":"3","key":"34_CR21","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"D. Shmoys","year":"1993","unstructured":"Shmoys, D., Tardos, E.: An approximation algorithm for the generalized assignment problem. Mathematical Programming\u00a062(3), 461\u2013474 (1993)","journal-title":"Mathematical Programming"},{"key":"34_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-540-85363-3_20","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. Srinivasan","year":"2008","unstructured":"Srinivasan, A.: Budgeted Allocations in the Full-Information Setting. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 247\u2013253. Springer, Heidelberg (2008)"},{"key":"34_CR23","doi-asserted-by":"crossref","unstructured":"Vondrak, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC (2008)","DOI":"10.1145\/1374376.1374389"}],"container-title":["Lecture Notes in Computer Science","Internet and Network Economics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10841-9_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,24]],"date-time":"2020-05-24T04:11:06Z","timestamp":1590293466000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10841-9_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642108402","9783642108419"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10841-9_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}