{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T10:37:43Z","timestamp":1764239863886},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319075563"},{"type":"electronic","value":"9783319075570"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07557-0_18","type":"book-chapter","created":{"date-parts":[[2014,5,17]],"date-time":"2014-05-17T11:50:30Z","timestamp":1400327430000},"page":"210-221","source":"Crossref","is-referenced-by-count":13,"title":["Submodular Maximization Meets Streaming: Matchings, Matroids, and More"],"prefix":"10.1007","author":[{"given":"Amit","family":"Chakrabarti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sagar","family":"Kale","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: Matchings, matroids, and more. arXiv preprint arXiv:1309.2038 (2013)","DOI":"10.1007\/978-3-319-07557-0_18"},{"issue":"2","key":"18_CR2","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. Theor. Comput. Sci.\u00a0348(2), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/11538462_15","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. McGregor","year":"2005","unstructured":"McGregor, A.: Finding graph matchings in data streams. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 170\u2013181. Springer, Heidelberg (2005)"},{"key":"18_CR4","unstructured":"Zelke, M.: Weighted matching in the semi-streaming model. In: Proc. 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008, pp. 669\u2013680 (2008)"},{"issue":"3","key":"18_CR5","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L. Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM Journal on Discrete Mathematics\u00a025(3), 1251\u20131265 (2011)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Goel, A., Kapralov, M., Khanna, S.: On the communication and streaming complexity of maximum bipartite matching. In: Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 468\u2013485. SIAM (2012)","DOI":"10.1137\/1.9781611973099.41"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Kapralov, M.: Better bounds for matchings in the streaming model. In: Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. SIAM (2013)","DOI":"10.1137\/1.9781611973105.121"},{"key":"18_CR8","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.\u00a06755, pp. 379\u2013390. Springer, Heidelberg (2011)"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1007\/978-3-642-22012-8_42","volume-title":"Automata, Languages and Programming","author":"K.J. Ahn","year":"2011","unstructured":"Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 526\u2013538. Springer, Heidelberg (2011)"},{"issue":"1","key":"18_CR10","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G. Nemhauser","year":"1978","unstructured":"Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of approximations for maximizing submodular set functions\u2014I. Mathematical Programming\u00a014(1), 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"18_CR11","series-title":"Mathematical Programming Studies","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume-title":"Polyhedral Combinatorics","author":"M. Fisher","year":"1978","unstructured":"Fisher, M., Nemhauser, G., Wolsey, L.: An analysis of approximations for maximizing submodular set functions\u2014II. In: Balinski, M., Hoffman, A. (eds.) Polyhedral Combinatorics. Mathematical Programming Studies, vol.\u00a08, pp. 73\u201387. Springer, Heidelberg (1978)"},{"issue":"6","key":"18_CR12","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.\u00a040(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"18_CR13","first-page":"323","volume-title":"Proc. 41st Annual ACM Symposium on the Theory of Computing, STOC 2009","author":"J. Lee","year":"2009","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, STOC 2009, pp. 323\u2013332. ACM, Bethesda (2009)"},{"issue":"4","key":"18_CR14","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. Mathematics of Operations Research\u00a035(4), 795\u2013806 (2010)","journal-title":"Mathematics of Operations Research"},{"key":"18_CR15","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.\u00a06942, pp. 784\u2013798. Springer, Heidelberg (2011)"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. SIAM (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"18_CR17","first-page":"170","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers, HLT 2011","author":"H. Lin","year":"2011","unstructured":"Lin, H., Bilmes, J.: Word alignment via submodular maximization over matroids. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers, HLT 2011, vol.\u00a02, pp. 170\u2013175. Association for Computational Linguistics, Stroudsburg (2011)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07557-0_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T21:24:06Z","timestamp":1558905846000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07557-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319075563","9783319075570"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07557-0_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}