{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T11:58:51Z","timestamp":1781092731734,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_26","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"318-330","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["Streaming Algorithms for Submodular Function Maximization"],"prefix":"10.1007","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shalmoli","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kent","family":"Quanrud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"26_CR1","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proc. 18th ACM-SIAM Sympos. Discrete Algs. (SODA), pp. 434\u2013443. Philadelphia, PA, USA (2007)"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: Streaming submodular optimization: massive data summarization on the fly. In: Proc. 20th ACM Conf. Knowl. Disc. and Data Mining (KDD), pp. 671\u2013680 (August 2014)","DOI":"10.1145\/2623330.2623637"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: Proc. 25th ACM-SIAM Sympos. Discrete Algs. (SODA), pp. 1497\u20131514 (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-642-22006-7_32","volume-title":"Automata, Languages and Programming","author":"A Badanidiyuru Varadaraja","year":"2011","unstructured":"Badanidiyuru Varadaraja, A.: Buyback problem - approximate matroid intersection with cancellation costs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 379\u2013390. Springer, Heidelberg (2011)"},{"issue":"1","key":"26_CR5","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4086\/toc.2012.v008a024","volume":"8","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: Solving packing integer programs via randomized rounding with alterations. Theo. Comput. 8(1), 533\u2013565 (2012)","journal-title":"Theo. Comput."},{"issue":"4","key":"26_CR6","first-page":"32:1","volume":"9","author":"M Bateni","year":"2013","unstructured":"Bateni, M., Hajiaghayi, M., Zadimoghaddam, M.: Submodular secretary problem and extensions. ACM Trans. Algs. 9(4), 32:1\u201332:23 (2013)","journal-title":"ACM Trans. Algs."},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. In: Proc. 53rd Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 649\u2013658 (2012)","DOI":"10.1109\/FOCS.2012.73"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proc. 25th ACM-SIAM Sympos. Discrete Algs. (SODA), pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973730.80"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Online submodular maximization with preemption. In: Proc. 26th ACM-SIAM Sympos. Discrete Algs. (SODA), pp. 1202\u20131216 (2015)","DOI":"10.1137\/1.9781611973730.80"},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 182\u2013196. Springer, Heidelberg (2007)"},{"issue":"6","key":"26_CR11","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-319-07557-0_18","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Chakrabarti","year":"2014","unstructured":"Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: matchings, matroids, and more. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 210\u2013221. Springer, Heidelberg (2014)"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Jayram, T.S., Vondr\u00e1k, J.: On multiplicative weight updates for concave and submodular function maximization. In: Proceedings of ITCS (2015)","DOI":"10.1145\/2688073.2688086"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proc. 43th Annu. ACM Sympos. Theory Comput. (STOC), pp. 783\u2013792 (2011)","DOI":"10.1145\/1993636.1993740"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proc. 16th ACM Conf. Knowl. Disc. and Data Mining (KDD), pp. 1029\u20131038 (2010)","DOI":"10.1145\/1835804.1835934"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: Proc. 15th ACM Conf. Knowl. Disc. and Data Mining (KDD), pp. 199\u2013208. New York, NY, USA (2009)","DOI":"10.1145\/1557019.1557047"},{"key":"26_CR17","unstructured":"Dasgupta, A., Kumar, R., Ravi, S.: Summarization through submodularity and dispersion. In: Proc. 51st Ann. Meet. Assoc. for Comp. Ling. (ACL), vol. 1, pp. 1014\u20131022 (2013)"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Vondrak, J.: From query complexity to computational complexity. In: Proc. 44th Annu. ACM Sympos. Theory Comput. (STOC), pp. 1107\u20131116 (2012)","DOI":"10.1145\/2213977.2214076"},{"issue":"2\u20133","key":"26_CR19","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theo. Comp. Sci. 348(2\u20133), 207\u2013216 (2005)","journal-title":"Theo. Comp. Sci."},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: Proc. 52nd Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 570\u2013579 (2011)","DOI":"10.1109\/FOCS.2011.46"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1007\/978-3-642-23719-5_66","volume-title":"Algorithms \u2013 ESA 2011","author":"M Feldman","year":"2011","unstructured":"Feldman, M., Naor, J.S., Schwartz, R., Ward, J.: Improved approximations for k-exchange systems. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 784\u2013798. Springer, Heidelberg (2011)"},{"issue":"2","key":"26_CR22","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/130920277","volume":"43","author":"Y Filmus","year":"2014","unstructured":"Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2), 514\u2013542 (2014)","journal-title":"SIAM J. Comput."},{"key":"26_CR23","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions - II. Math. Prog. Studies 8, 73\u201387 (1978)","journal-title":"Math. Prog. Studies"},{"key":"26_CR24","unstructured":"Fujishige, S.: Submodular functions and optimization, vol. 58. Elsevier (2005)"},{"issue":"1","key":"26_CR25","doi-asserted-by":"publisher","first-page":"73","DOI":"10.14778\/2047485.2047492","volume":"5","author":"A Goyal","year":"2011","unstructured":"Goyal, A., Bonchi, F., Lakshmanan, L.V.S.: A data-based approach to social influence maximization. Proc. VLDB Endow. 5(1), 73\u201384 (2011)","journal-title":"Proc. VLDB Endow."},{"key":"26_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-17572-5_20","volume-title":"Internet and Network Economics","author":"A Gupta","year":"2010","unstructured":"Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: offline and secretary algorithms. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 246\u2013257. Springer, Heidelberg (2010)"},{"key":"26_CR27","unstructured":"Iyer, R., Jegelka, S., Bilmes, J.: Fast semidifferential-based submodular function optimization. In: Proc. 30th Int. Conf. Mach. Learning (ICML), vol. 28, pp. 855\u2013863 (2013)"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: Proc. 9th ACM Conf. Knowl. Disc. and Data Mining (KDD), pp. 137\u2013146. New York, NY, USA (2003)","DOI":"10.1145\/956750.956769"},{"issue":"4","key":"26_CR29","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1287\/moor.2013.0592","volume":"38","author":"A Kulik","year":"2013","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math. Oper. Res. 38(4), 729\u2013739 (2013)","journal-title":"Math. Oper. Res."},{"key":"26_CR30","doi-asserted-by":"crossref","unstructured":"Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in mapreduce and streaming. In: Proc. 25th Ann. ACM Sympos. Parallelism Alg. Arch. (SPAA), pp. 1\u201310 (2013)","DOI":"10.1145\/2486159.2486168"},{"issue":"4","key":"26_CR31","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1137\/090750020","volume":"23","author":"J Lee","year":"2010","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math. 23(4), 2053\u20132078 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"26_CR32","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35, 795\u2013806 (2010)","journal-title":"Math. Oper. Res."},{"key":"26_CR33","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., Glance, N.: Cost-effective outbreak detection in networks. In: Proc. 13th ACM Conf. Knowl. Disc. and Data Mining (KDD), pp. 420\u2013429. New York, NY, USA (2007)","DOI":"10.1145\/1281192.1281239"},{"key":"26_CR34","unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proc. 49th Ann. Meet. Assoc. Comput. Ling.: Human Lang. Tech. (HLT), vol. 1, pp. 510\u2013520 (2011)"},{"key":"26_CR35","doi-asserted-by":"crossref","unstructured":"McGregor, A.: Finding graph matchings in data streams. In: 8th Intl. Work. Approx. Algs. Combin. Opt. Problems, pp. 170\u2013181 (2005)","DOI":"10.1007\/11538462_15"},{"issue":"1","key":"26_CR36","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions - I. Math. Prog. 14(1), 265\u2013294 (1978)","journal-title":"Math. Prog."},{"key":"26_CR37","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol. 24. Springer Verlag (2003)"},{"key":"26_CR38","doi-asserted-by":"crossref","unstructured":"Seeman, L., Singer, Y.: Adaptive seeding in social networks. In: Proc. 54th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 459\u2013468 (2013)","DOI":"10.1109\/FOCS.2013.56"},{"key":"26_CR39","doi-asserted-by":"crossref","unstructured":"Sipos, R., Swaminathan, A., Shivaswamy, P., Joachims, T.: Temporal corpus summarization using submodular word coverage. In: Proc. 21st ACM Int. Conf. Inf. and Know. Management (CIKM), pp. 754\u2013763 (2012)","DOI":"10.1145\/2396761.2396857"},{"issue":"1","key":"26_CR40","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1137\/110832318","volume":"42","author":"J Vondr\u00e1k","year":"2013","unstructured":"Vondr\u00e1k, J.: Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1), 265\u2013304 (2013)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T16:20:34Z","timestamp":1674836434000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}