{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:02Z","timestamp":1740109322482,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-184656"],"award-info":[{"award-number":["200021-184656"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the <jats:italic>unweighted<\/jats:italic> matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is based on the versatile local ratio technique and also applies to generalizations such as weighted hypergraph matchings. However, the framework for the analysis fails for the related problem of weighted matroid intersection and as a result the approximation guarantee for weighted instances did not match the factor 2 achieved by the greedy algorithm for unweighted instances.Our main result closes this gap by developing a semi-streaming algorithm with an approximation guarantee of <jats:inline-formula><jats:alternatives><jats:tex-math>$$2+\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for <jats:italic>weighted<\/jats:italic> matroid intersection, improving upon the previous best guarantee of <jats:inline-formula><jats:alternatives><jats:tex-math>$$4+\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>4<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our techniques also allow us to generalize recent results by Levin and Wajc on submodular maximization subject to matching constraints to that of matroid-intersection constraints. While our algorithm is an adaptation of the local ratio technique used in previous works, the analysis deviates significantly and relies on structural properties of matroid intersection, called kernels. Finally, we also conjecture that our algorithm gives a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(k+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> approximation for the intersection of <jats:italic>k<\/jats:italic> matroids but prove that new tools are needed in the analysis as the structural properties we use fail for <jats:inline-formula><jats:alternatives><jats:tex-math>$$k\\ge 3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. \n<\/jats:p>","DOI":"10.1007\/s10107-022-01858-9","type":"journal-article","created":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T18:33:26Z","timestamp":1659119606000},"page":"967-990","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Semi-streaming algorithms for submodular matroid intersection"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6306-3389","authenticated-orcid":false,"given":"Paritosh","family":"Garg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linus","family":"Jordan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"1858_CR1","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints, In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, SIAM, pp.\u00a01433\u20131452 (2014)","DOI":"10.1137\/1.9781611973730.80"},{"key":"1858_CR2","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/1041680.1041683","volume":"36","author":"R Bar-Yehuda","year":"2004","unstructured":"Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: A unified framework for approximation algorithms. in memoriam: Shimon even 1935-2004. ACM Computing Surveys (CSUR) 36, 422\u2013463 (2004)","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"1858_CR3","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem, Analysis and Design of Algorithms for Combinatorial Problems (G.\u00a0Ausiello and M.\u00a0Lucertini, eds.), North-Holland Mathematics Studies, vol. 109, North-Holland, pp.\u00a027 \u2013 45 (1985)","DOI":"10.1016\/S0304-0208(08)73101-3"},{"issue":"1","key":"1858_CR4","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), 225\u2013247 (2015)","journal-title":"Math. Program."},{"key":"1858_CR5","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":"1858_CR6","series-title":"In: Annals of Discrete Mathematics","first-page":"39","volume-title":"Matroid intersection, Discrete Optimization I","author":"J Edmonds","year":"1979","unstructured":"Edmonds, J.: Matroid intersection, Discrete Optimization I. In: Annals of Discrete Mathematics, vol. 4, pp. 39\u201349. Elsevier, Amsterdam, Netherlands (1979)"},{"issue":"2\u20133","key":"1858_CR7","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. Theoret. Comput. Sci. 348(2\u20133), 207\u2013216 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"1858_CR8","series-title":"In: International Conference on Integer Programming and Combinatorial Optimization","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-45535-3_9","volume-title":"A Matroid Generalization of the Stable Matching Polytope","author":"T Fleiner","year":"2001","unstructured":"Fleiner, T.: A Matroid Generalization of the Stable Matching Polytope. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 105\u2013114. Springer, Berlin (2001)"},{"key":"1858_CR9","unstructured":"Ghaffari, M., Wajc, D.: Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching, 2nd Symposium on Simplicity in Algorithms (SOSA 2019) (Dagstuhl, Germany) (Jeremy\u00a0T. Fineman and Michael Mitzenmacher, eds.), OpenAccess Series in Informatics (OASIcs), vol.\u00a069, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, pp.\u00a013:1\u201313:8 (2018)"},{"key":"1858_CR10","unstructured":"Huang, C.-C., Kakimura, N., Mauras, S., Yoshida, Y.: Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model, CoRR arXiv:2002.05477 (2020)"},{"key":"1858_CR11","doi-asserted-by":"crossref","unstructured":"Levin, R., Wajc, D.: Streaming submodular matching meets the primal-dual method, In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp.\u00a01914\u20131933 (2021)","DOI":"10.1137\/1.9781611976465.114"},{"key":"1858_CR12","doi-asserted-by":"crossref","unstructured":"McGregor, A.: Finding graph matchings in data streams, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (Berlin, Heidelberg) (Chandra Chekuri, Klaus Jansen, Jos\u00e9 D.\u00a0P. Rolim, and Luca Trevisan, eds.), Springer Berlin Heidelberg, pp.\u00a0170\u2013181 (2005)","DOI":"10.1007\/11538462_15"},{"issue":"2","key":"1858_CR13","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."},{"issue":"2","key":"1858_CR14","first-page":"1","volume":"15","author":"A Paz","year":"2018","unstructured":"Paz, A., Schwartzman, G.: A (2+ $$\\varepsilon $$)-approximation for maximum weight matching in the semi-streaming model. ACM Transactions on Algorithms (TALG) 15(2), 1\u201315 (2018)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"1858_CR15","series-title":"In: Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. In: Algorithms and Combinatorics, Springer, Berlin (2003)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01858-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01858-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01858-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:21:26Z","timestamp":1675704086000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01858-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,27]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1858"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01858-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2022,7,27]]},"assertion":[{"value":"1 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}