{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T21:51:24Z","timestamp":1768773084447,"version":"3.49.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T00:00:00Z","timestamp":1732924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ERC","award":["788893"],"award-info":[{"award-number":["788893"]}]},{"name":"AMDROMA \u201cAlgorithmic and Mechanism Design Research in Online Markets\u201d, PNRR MUR","award":["PE0000013-FAIR"],"award-info":[{"award-number":["PE0000013-FAIR"]}]},{"name":"PNRR MUR","award":["IR0000013"],"award-info":[{"award-number":["IR0000013"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"<jats:p>\n            Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this significant problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({\\tilde{O}(\\frac{{k^{2}}}{{\\varepsilon}})}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            amortized update time (in the number of insertions and deletions) and yields a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({(4+O(\\varepsilon))}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximate solution with respect to the dynamic optimum, where\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is the rank of the matroid.\n          <\/jats:p>","DOI":"10.1145\/3698397","type":"journal-article","created":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T14:09:51Z","timestamp":1729087791000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Fully Dynamic Submodular Maximization over Matroids"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0635-6812","authenticated-orcid":false,"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[{"name":"Google Research, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6250-945X","authenticated-orcid":false,"given":"Federico","family":"Fusco","sequence":"additional","affiliation":[{"name":"Department of Computer, Control and Management Engineering \u201cAntonio Ruberti\u201d, Sapienza University of Rome, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3502-7559","authenticated-orcid":false,"given":"Silvio","family":"Lattanzi","sequence":"additional","affiliation":[{"name":"Google Research, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2336-9826","authenticated-orcid":false,"given":"Ashkan","family":"Norouzi-Fard","sequence":"additional","affiliation":[{"name":"Google Research, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0717-1120","authenticated-orcid":false,"given":"Morteza","family":"Zadimoghaddam","sequence":"additional","affiliation":[{"name":"Google Research, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,30]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1613\/jair.1.13472","article-title":"Fast adaptive non-monotone submodular maximization subject to a knapsack constraint","volume":"74","author":"Amanatidis Georgios","year":"2022","unstructured":"Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenh\u00e4user. 2022. Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. The Journal of Artificial Intelligence Research 74 (2022), 661\u2013690.","journal-title":"The Journal of Artificial Intelligence Research"},{"key":"e_1_3_2_3_2","first-page":"148","volume-title":"KDD","author":"Avdiukhin Dmitrii","year":"2019","unstructured":"Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou. 2019. Adversarially robust submodular maximization under knapsack constraints. In KDD. ACM, New York, NY, 148\u2013156."},{"key":"e_1_3_2_4_2","first-page":"118","volume-title":"NIPS","author":"Bach Francis R.","year":"2010","unstructured":"Francis R. Bach. 2010. Structured sparsity-inducing norms through submodular functions. In NIPS. Curran Associates, Inc., 118\u2013126."},{"key":"e_1_3_2_5_2","first-page":"671","volume-title":"KDD","author":"Badanidiyuru Ashwinkumar","year":"2014","unstructured":"Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. 2014. Streaming submodular maximization: Massive data summarization on the fly. In KDD. ACM, New York, NY, 671\u2013680."},{"key":"e_1_3_2_6_2","first-page":"553","article-title":"Summarization of multi-document topic hierarchies using submodular mixtures","author":"Bairi Ramakrishna","year":"2015","unstructured":"Ramakrishna Bairi, Rishabh K. Iyer, Ganesh Ramakrishnan, and Jeff A. Bilmes. 2015. Summarization of multi-document topic hierarchies using submodular mixtures. In ACL. The Association for Computer Linguistics, 553\u2013563.","journal-title":"ACL"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"Kiarash Banihashem Leyla Biabani Samira Goudarzi MohammadTaghi Hajiaghayi Peyman Jabbarzade and Morteza Monemizadeh. 2023. Dynamic algorithms for matroid submodular maximization. arXiv:2306.00959. Retrieved from https:\/\/arxiv.org\/abs\/2306.00959","DOI":"10.1137\/1.9781611977912.125"},{"key":"e_1_3_2_8_2","first-page":"1660","volume-title":"ICML, Proceedings of Machine Learning Research","author":"Banihashem Kiarash","year":"2023","unstructured":"Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. 2023. Dynamic constrained submodular optimization with polylogarithmic update time. In ICML, Proceedings of Machine Learning Research, Vol. 202, PMLR, 1660\u20131691."},{"key":"e_1_3_2_9_2","first-page":"3485","volume-title":"SODA","author":"Banihashem Kiarash","year":"2024","unstructured":"Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. 2024. Dynamic algorithms for matroid submodular maximization. In SODA. SIAM, 3485\u20133533."},{"key":"e_1_3_2_10_2","first-page":"508","article-title":"Robust submodular maximization: A non-uniform partitioning approach","author":"Bogunovic Ilija","year":"2017","unstructured":"Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher. 2017. Robust submodular maximization: A non-uniform partitioning approach. In ICML. PMLR, 508\u2013516.","journal-title":"ICML"},{"issue":"6","key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","article-title":"Maximizing a monotone submodular function subject to a matroid constraint","volume":"40","author":"C\u0103linescu Gruia","year":"2011","unstructured":"Gruia C\u0103linescu, Chandra Chekuri, Martin P\u00e1l, and Jan Vondr\u00e1k. 2011. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40, 6 (2011), 1740\u20131766.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0900-7"},{"key":"e_1_3_2_13_2","first-page":"318","volume-title":"ICALP (1), Lecture Notes in Computer Science","author":"Chekuri Chandra","year":"2015","unstructured":"Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. 2015. Streaming algorithms for submodular function maximization. In ICALP (1), Lecture Notes in Computer Science, Vol. 9134, Springer, 318\u2013330."},{"key":"e_1_3_2_14_2","unstructured":"Jiecao Chen Huy L. Nguyen and Qin Zhang. 2016. Submodular maximization over sliding windows. arXiv:1611.00129. Retrieved from https:\/\/arxiv.org\/abs\/1611.00129"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519951"},{"key":"e_1_3_2_16_2","first-page":"1057","volume-title":"ICML","author":"Das Abhimanyu","year":"2011","unstructured":"Abhimanyu Das and David Kempe. 2011. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In ICML. Omnipress, 1057\u20131064."},{"key":"e_1_3_2_17_2","first-page":"346","volume-title":"PerCom Workshops","author":"Dey Ratan","year":"2012","unstructured":"Ratan Dey, Zubin Jelveh, and Keith W. Ross. 2012. Facebook users have become much more private: A large-scale study. In PerCom Workshops. IEEE Computer Society, 346\u2013352."},{"key":"e_1_3_2_18_2","first-page":"5671","volume-title":"ICML, Proceedings of Machine Learning Research","author":"Duetting Paul","year":"2022","unstructured":"Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. 2022. Deletion robust submodular maximization over matroids. In ICML, Proceedings of Machine Learning Research, Vol. 162, PMLR, 5671\u20135693."},{"key":"e_1_3_2_19_2","first-page":"8821","volume-title":"ICML, Proceedings of Machine Learning Research","author":"Duetting Paul","year":"2023","unstructured":"Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, and Morteza Zadimoghaddam. 2023. Fully dynamic submodular maximization over matroids. In ICML, Proceedings of Machine Learning Research, Vol. 202, PMLR, 8821\u20138835."},{"key":"e_1_3_2_20_2","unstructured":"Paul D\u00fctting Federico Fusco Silvio Lattanzi Ashkan Norouzi-Fard and Morteza Zadimoghaddam. 2022. Deletion robust non-monotone submodular maximization over matroids. arXiv:2208.07582v1. Retrieved from https:\/\/arxiv.org\/abs\/2208.07582"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","unstructured":"Paul D\u00fctting Federico Fusco Silvio Lattanzi Ashkan Norouzi-Fard and Morteza Zadimoghaddam. 2023. Fully dynamic submodular maximization over matroids. arXiv:2305.19918. Retrieved from https:\/\/arxiv.org\/abs\/2305.19918","DOI":"10.1145\/3698397"},{"key":"e_1_3_2_22_2","first-page":"54:1","article-title":"Towards nearly-linear time algorithms for submodular maximization with a matroid constraint","volume":"132","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Huy L. Nguyen. 2019. Towards nearly-linear time algorithms for submodular maximization with a matroid constraint. In ICALP, LIPIcs, Vol. 132, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 54:1\u201354:14.","journal-title":"ICALP, LIPIcs"},{"key":"e_1_3_2_23_2","first-page":"421","volume-title":"WWW","author":"Epasto Alessandro","year":"2017","unstructured":"Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam. 2017. Submodular optimization over sliding windows. In WWW. ACM, New York, NY, 421\u2013430."},{"issue":"4","key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of ln n for approximating set cover","volume":"45","author":"Feige Uriel","year":"1998","unstructured":"Uriel Feige. 1998. A threshold of ln n for approximating set cover. The Journal of the ACM 45, 4 (1998), 634\u2013652.","journal-title":"The Journal of the ACM"},{"key":"e_1_3_2_25_2","first-page":"730","article-title":"Do less, get more: Streaming submodular maximization with subsampling","author":"Feldman Moran","year":"2018","unstructured":"Moran Feldman, Amin Karbasi, and Ehsan Kazemi. 2018. Do less, get more: Streaming submodular maximization with subsampling. In NeurIPS, 730\u2013740.","journal-title":"NeurIPS"},{"key":"e_1_3_2_26_2","first-page":"59:1","article-title":"Streaming submodular maximization under matroid constraints","author":"Feldman Moran","year":"2022","unstructured":"Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. 2022. Streaming submodular maximization under matroid constraints. In ICALP, 59:1\u201359:20.","journal-title":"ICALP"},{"key":"e_1_3_2_27_2","first-page":"1363","volume-title":"STOC","author":"Feldman Moran","year":"2020","unstructured":"Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. 2020. The one-way communication complexity of submodular maximization with applications to streaming and robustness. In STOC. ACM, New York, NY, 1363\u20131374."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208448"},{"key":"e_1_3_2_30_2","article-title":"Fairness in streaming submodular maximization: Algorithms and hardness","author":"Halabi Marwa El","year":"2020","unstructured":"Marwa El Halabi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub Tarnawski. 2020. Fairness in streaming submodular maximization: Algorithms and hardness. In NeurIPS.","journal-title":"NeurIPS"},{"key":"e_1_3_2_31_2","first-page":"2549","volume-title":"ICML","author":"Kazemi Ehsan","year":"2018","unstructured":"Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. 2018. Scalable deletion-robust submodular maximization: data summarization with privacy and fairness constraints. In ICML. PMLR, 2549\u20132558."},{"key":"e_1_3_2_32_2","article-title":"Fully dynamic algorithm for constrained submodular optimization","author":"Lattanzi Silvio","year":"2020","unstructured":"Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Morteza Zadimoghaddam. 2020. Fully dynamic algorithm for constrained submodular optimization. In NeurIPS.","journal-title":"NeurIPS"},{"key":"e_1_3_2_33_2","unstructured":"Silvio Lattanzi Slobodan Mitrovic Ashkan Norouzi-Fard Jakub Tarnawski and Morteza Zadimoghaddam. 2023. Fully dynamic algorithm for constrained submodular optimization. arXiv:2006.04704. Retrieved from https:\/\/arxiv.org\/abs\/2006.04704"},{"key":"e_1_3_2_34_2","first-page":"510","volume-title":"ACL","author":"Lin Hui","year":"2011","unstructured":"Hui Lin and Jeff A. Bilmes. 2011. A class of submodular functions for document summarization. In ACL. The Association for Computer Linguistics, 510\u2013520."},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/BFb0006528","volume-title":"Optimization Techniques","author":"Minoux Michel","year":"1978","unstructured":"Michel Minoux. 1978. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques. Springer, 234\u2013243."},{"key":"e_1_3_2_36_2","first-page":"2449","volume-title":"ICML, Proceedings of Machine Learning Research","volume":"70","author":"Mirzasoleiman Baharan","year":"2017","unstructured":"Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. 2017. Deletion-robust submodular maximization: data summarization with \u201cthe right to be forgotten\u201d. In ICML, Proceedings of Machine Learning Research, Vol. 70, PMLR, 2449\u20132458."},{"key":"e_1_3_2_37_2","first-page":"4557","article-title":"Streaming robust submodular maximization: A partitioned thresholding approach","author":"Mitrovic Slobodan","year":"2017","unstructured":"Slobodan Mitrovic, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Volkan Cevher. 2017. Streaming robust submodular maximization: A partitioned thresholding approach. In NIPS, 4557\u20134566.","journal-title":"NIPS"},{"key":"e_1_3_2_38_2","article-title":"Dynamic submodular maximization","author":"Monemizadeh Morteza","year":"2020","unstructured":"Morteza Monemizadeh. 2020. Dynamic submodular maximization. In NeurIPS.","journal-title":"NeurIPS"},{"issue":"1","key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s10107-018-1320-2","article-title":"Robust monotone submodular function maximization","volume":"172","author":"Orlin James B.","year":"2018","unstructured":"James B. Orlin, Andreas S. Schulz, and Rajan Udwani. 2018. Robust monotone submodular function maximization. Mathematical Programming: Series A and B 172, 1 (2018), 505\u2013537.","journal-title":"Mathematical Programming: Series A and B"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM54844.2022.00078"},{"key":"e_1_3_2_41_2","unstructured":"Guangyi Zhang Nikolaj Tatti and Aristides Gionis. 2022. Optimal deletion-robust coreset for submodular maximization. arXiv:2203.01241. Retrieved from https:\/\/arxiv.org\/abs\/2203.01241"},{"key":"e_1_3_2_42_2","first-page":"1341","article-title":"Submodular attribute selection for action recognition in video","author":"Zheng Jingjing","year":"2014","unstructured":"Jingjing Zheng, Zhuolin Jiang, Rama Chellappa, and P. Jonathon Phillips. 2014. Submodular attribute selection for action recognition in video. In NIPS, 1341\u20131349.","journal-title":"NIPS"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698397","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:34Z","timestamp":1750294714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,30]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3698397"],"URL":"https:\/\/doi.org\/10.1145\/3698397","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,30]]},"assertion":[{"value":"2023-09-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}