{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:10Z","timestamp":1740109330292,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T00:00:00Z","timestamp":1726272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T00:00:00Z","timestamp":1726272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"agence nationale de la recherche","doi-asserted-by":"publisher","award":["ANR-19-CE48-0016","ANR-18-CE40-0025-01"],"award-info":[{"award-number":["ANR-19-CE48-0016","ANR-18-CE40-0025-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,11]]},"DOI":"10.1007\/s00453-024-01272-x","type":"journal-article","created":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T08:02:47Z","timestamp":1726300967000},"page":"3598-3628","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Semi-streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints"],"prefix":"10.1007","volume":"86","author":[{"given":"Chien-Chung","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4531-2027","authenticated-orcid":false,"given":"Fran\u00e7ois","family":"Sellier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,14]]},"reference":[{"key":"1272_CR1","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proc. 25th SODA, pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973402.106"},{"issue":"1\u20132","key":"1272_CR2","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-015-0900-7","volume":"154","author":"A Chakrabarti","year":"2015","unstructured":"Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: matchings, matroids, and more. Math. Program. 154(1\u20132), 225\u2013247 (2015)","journal-title":"Math. Program."},{"key":"1272_CR3","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Gupta, S., Quanrud, K.: Streaming algorithms for submodular function maximization. In: Proc. 42nd ICALP, pp. 318\u2013330 (2015)","DOI":"10.1007\/978-3-662-47672-7_26"},{"key":"1272_CR4","first-page":"96","volume":"28","author":"M Crouch","year":"2014","unstructured":"Crouch, M., Stubbs, D.M.: Improved streaming algorithms for weighted matching, via unweighted matching. Leibniz Int. Proc. Inform. LIPIcs 28, 96\u2013104 (2014)","journal-title":"Leibniz Int. Proc. Inform. LIPIcs"},{"key":"1272_CR5","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L Epstein","year":"2009","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discret. Math. 25, 1251\u20131265 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"1272_CR6","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. 348, 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1272_CR7","unstructured":"Feldman, M., Karbasi, A., Kazemi, E.: Do less, get more: streaming submodular maximization with subsampling. In: NeurIPS, pp. 730\u2013740 (2018)"},{"key":"1272_CR8","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J.\u00a0(Seffi), Schwartz, R., Ward, J.: Improved approximations for k-exchange systems. In: Proc. 19th ESA, pp. 784\u2013798 (2011)","DOI":"10.1007\/978-3-642-23719-5_66"},{"key":"1272_CR9","doi-asserted-by":"crossref","unstructured":"Garg, P., Jordan, L., Svensson, O.: Semi-streaming algorithms for submodular matroid intersection. In: IPCO (2021)","DOI":"10.1007\/978-3-030-73879-2_15"},{"key":"1272_CR10","unstructured":"Ghaffari, M., Wajc, D.: Simplified and space-optimal semi-streaming (2+$$\\varepsilon $$)-approximate matching. In: Fineman, J.T., Mitzenmacher, M. (eds.) 2nd Symposium on Simplicity in Algorithms (SOSA 2019), volume\u00a069 of OpenAccess Series in Informatics (OASIcs), pp. 13:1\u201313:8, Dagstuhl, Germany (2018). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik"},{"key":"1272_CR11","unstructured":"Huang, C.-C., Sellier, F.: Semi-streaming algorithms for submodular function maximization under $$b$$-matching constraint. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2021) (2021)"},{"key":"1272_CR12","doi-asserted-by":"crossref","unstructured":"Levin, R., Wajc, D.: Streaming submodular matching meets the primal-dual method. In SODA, pp. 1914\u20131933 (2021)","DOI":"10.1137\/1.9781611976465.114"},{"key":"1272_CR13","doi-asserted-by":"crossref","unstructured":"McGregor, A.: Finding graph matchings in data streams. In: Chekuri, C, Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pp. 170\u2013181. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)","DOI":"10.1007\/11538462_15"},{"issue":"2","key":"1272_CR14","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci. 1(2), 117\u2013236 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"1272_CR15","doi-asserted-by":"crossref","unstructured":"Paz, A., Schwartzman, G.: A $$(2 + \\varepsilon )$$-approximation for maximum weight matching in the semi-streaming model. In: Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2153\u20132161 (2017)","DOI":"10.1137\/1.9781611974782.140"},{"key":"1272_CR16","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol.\u00a024. Springer Science & Business Media (2003)"},{"key":"1272_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-010-9438-5","volume":"62","author":"M Zelke","year":"2008","unstructured":"Zelke, M.: Weighted matching in the semi-streaming model. Algorithmica 62, 1\u201320 (2008)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01272-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01272-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01272-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T09:02:24Z","timestamp":1728810144000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01272-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,14]]},"references-count":17,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1272"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01272-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,9,14]]},"assertion":[{"value":"31 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}