{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:21Z","timestamp":1750219821404,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62172384, U20A20182, 61873177"],"award-info":[{"award-number":["62172384, U20A20182, 61873177"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2018AAA0101204"],"award-info":[{"award-number":["2018AAA0101204"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>\n            It is of great importance to design streaming algorithms for submodular maximization, as many applications (e.g., crowdsourcing) have large volume of data satisfying the well-known ''diminishing returns'' property, which cannot be handled by offline algorithms requiring full access to the whole dataset. However, streaming submodular maximization has been less studied than the offline algorithms due to the hardness brought by more stringent requirements on memory consumption. In this paper, we consider the fundamental problem of Submodular Maximization under\n            <jats:italic>k<\/jats:italic>\n            -System and\n            <jats:italic>d<\/jats:italic>\n            -Knapsack constraints (SMSK), which has only been successfully addressed by offline algorithms in previous studies, and we propose the first streaming algorithm for it with provable performance bounds. Our approach adopts a novel algorithmic framework dubbed\n            <jats:sc>MultiplexGreedy<\/jats:sc>\n            , making it also perform well under a single\n            <jats:italic>k<\/jats:italic>\n            -system constraint. For the special case of SMSK with only\n            <jats:italic>d<\/jats:italic>\n            -knapsack constraints, we further propose a streaming algorithm with better performance ratios than the state-of-the-art algorithms. As the SMSK problem generalizes most of the major problems studied in submodular maximization, our algorithms have wide applications in big data processing.\n          <\/jats:p>","DOI":"10.1145\/3570615","type":"journal-article","created":{"date-parts":[[2022,12,8]],"date-time":"2022-12-08T20:20:10Z","timestamp":1670530810000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Streaming Algorithms for Constrained Submodular Maximization"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6080-4850","authenticated-orcid":false,"given":"Shuang","family":"Cui","sequence":"first","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6302-5366","authenticated-orcid":false,"given":"Kai","family":"Han","sequence":"additional","affiliation":[{"name":"Soochow University, Suzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0785-707X","authenticated-orcid":false,"given":"Jing","family":"Tang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou) &amp; The Hong Kong University of Science and Technology, China, Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2768-6607","authenticated-orcid":false,"given":"He","family":"Huang","sequence":"additional","affiliation":[{"name":"Soochow University, Suzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3699-0697","authenticated-orcid":false,"given":"Xueying","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3771-0199","authenticated-orcid":false,"given":"Zhiyu","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,12,8]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints","volume":"168","author":"Alaluf Naor","year":"2020","unstructured":"Naor Alaluf , Alina Ene , Moran Feldman , Huy L. Nguyen , and Andrew Suh . 2020 . Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints . In International Colloquium on Automata, Languages, and Programming (ICALP) , Vol. 168. 6: 1 -- 6 :19. Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. 2020. Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. In International Colloquium on Automata, Languages, and Programming (ICALP), Vol. 168. 6:1--6:19.","journal-title":"International Colloquium on Automata, Languages, and Programming (ICALP)"},{"key":"e_1_2_1_2_1","unstructured":"Georgios Amanatidis Federico Fusco Philip Lazos Stefano Leonardi and Rebecca Reiffenhauser. 2020. Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In Advances in Neural Information Processing Systems (NeurIPS).  Georgios Amanatidis Federico Fusco Philip Lazos Stefano Leonardi and Rebecca Reiffenhauser. 2020. Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_2_1_3_1","first-page":"524","article-title":"Submodular maximization through barrier functions","volume":"33","author":"Badanidiyuru Ashwinkumar","year":"2020","unstructured":"Ashwinkumar Badanidiyuru , Amin Karbasi , Ehsan Kazemi , and Jan Vondr\u00e1k . 2020 . Submodular maximization through barrier functions . In Advances in Neural Information Processing Systems (NeurIPS) , Vol. 33. 524 -- 534 . Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, and Jan Vondr\u00e1k. 2020. Submodular maximization through barrier functions. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 33. 524--534.","journal-title":"Advances in Neural Information Processing Systems (NeurIPS)"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"key":"e_1_2_1_6_1","unstructured":"Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone submodular maximization in exponentially fewer iterations. In Advances in Neural Information Processing Systems (NeurIPS).  Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone submodular maximization in exponentially fewer iterations. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0955"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Chandra Chekuri Shalmoli Gupta and Kent Quanrud. 2015. Streaming algorithms for submodular function maximization. In International Colloquium on Automata Languages and Programming (ICALP). 318--330.  Chandra Chekuri Shalmoli Gupta and Kent Quanrud. 2015. Streaming algorithms for submodular function maximization. In International Colloquium on Automata Languages and Programming (ICALP). 318--330.","DOI":"10.1007\/978-3-662-47672-7_26"},{"key":"e_1_2_1_10_1","volume-title":"International Conference on Machine Learning (ICML). 2222--2232","author":"Cui Shuang","year":"2021","unstructured":"Shuang Cui , Kai Han , Tianshuai Zhu , Jing Tang , Benwei Wu , and He Huang . 2021 . Randomized Algorithms for Submodular Function Maximization with a $ k $-System Constraint . In International Conference on Machine Learning (ICML). 2222--2232 . Shuang Cui, Kai Han, Tianshuai Zhu, Jing Tang, Benwei Wu, and He Huang. 2021. Randomized Algorithms for Submodular Function Maximization with a $ k $-System Constraint. In International Conference on Machine Learning (ICML). 2222--2232."},{"key":"e_1_2_1_11_1","first-page":"1","article-title":"A nearly-linear time algorithm for submodular maximization with a knapsack constraint","volume":"53","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Huy L. Nguyen . 2019 . A nearly-linear time algorithm for submodular maximization with a knapsack constraint . In International Colloquium on Automata, Languages and Programming (ICALP). 53 : 1 -- 53 :12. Alina Ene and Huy L. Nguyen. 2019. A nearly-linear time algorithm for submodular maximization with a knapsack constraint. In International Colloquium on Automata, Languages and Programming (ICALP). 53:1--53:12.","journal-title":"International Colloquium on Automata, Languages and Programming (ICALP)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2011.10.002"},{"key":"e_1_2_1_13_1","volume-title":"International Conference on Machine Learning (ICML). 1833--1842","author":"Fahrbach Matthew","year":"2019","unstructured":"Matthew Fahrbach , Vahab Mirrokni , and Morteza Zadimoghaddam . 2019 . Non-monotone submodular maximization with nearly optimal adaptivity and query complexity . In International Conference on Machine Learning (ICML). 1833--1842 . Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. 2019. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In International Conference on Machine Learning (ICML). 1833--1842."},{"key":"e_1_2_1_14_1","volume-title":"Conference on Learning Theory (COLT). 758--784","author":"Feldman Moran","year":"2017","unstructured":"Moran Feldman , Christopher Harshaw , and Amin Karbasi . 2017 . Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization . In Conference on Learning Theory (COLT). 758--784 . Moran Feldman, Christopher Harshaw, and Amin Karbasi. 2017. Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization. In Conference on Learning Theory (COLT). 758--784."},{"key":"e_1_2_1_15_1","volume-title":"How Do You Want Your Greedy: Simultaneous or Repeated? arXiv preprint arXiv:2009.13998","author":"Feldman Moran","year":"2020","unstructured":"Moran Feldman , Christopher Harshaw , and Amin Karbasi . 2020. How Do You Want Your Greedy: Simultaneous or Repeated? arXiv preprint arXiv:2009.13998 ( 2020 ). Moran Feldman, Christopher Harshaw, and Amin Karbasi. 2020. How Do You Want Your Greedy: Simultaneous or Repeated? arXiv preprint arXiv:2009.13998 (2020)."},{"key":"e_1_2_1_16_1","unstructured":"Moran Feldman Amin Karbasi and Ehsan Kazemi. 2018. Do less get more: Streaming submodular maximization with subsampling. In Advances in Neural Information Processing Systems (NeurIPS). 732--742.  Moran Feldman Amin Karbasi and Ehsan Kazemi. 2018. Do less get more: Streaming submodular maximization with subsampling. In Advances in Neural Information Processing Systems (NeurIPS). 732--742."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.63"},{"key":"e_1_2_1_19_1","volume-title":"International Conference on Machine Learning (ICML). 391--398","author":"Gomes Ryan","year":"2010","unstructured":"Ryan Gomes and Andreas Krause . 2010 . Budgeted nonparametric learning from data streams . In International Conference on Machine Learning (ICML). 391--398 . Ryan Gomes and Andreas Krause. 2010. Budgeted nonparametric learning from data streams. In International Conference on Machine Learning (ICML). 391--398."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17572-5_20"},{"key":"e_1_2_1_21_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Haba Ran","year":"2020","unstructured":"Ran Haba , Ehsan Kazemi , Moran Feldman , and Amin Karbasi . 2020 . Streaming Submodular Maximization under a k-Set System Constraint . In International Conference on Machine Learning (ICML). Ran Haba, Ehsan Kazemi, Moran Feldman, and Amin Karbasi. 2020. Streaming Submodular Maximization under a k-Set System Constraint. In International Conference on Machine Learning (ICML)."},{"key":"e_1_2_1_22_1","unstructured":"Kai Han Zongmai Cao Shuang Cui and Benwei Wu. 2020. Deterministic approximation for submodular maximization over a matroid in nearly linear time. In Advances in Neural Information Processing Systems (NeurIPS).  Kai Han Zongmai Cao Shuang Cui and Benwei Wu. 2020. Deterministic approximation for submodular maximization over a matroid in nearly linear time. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447383"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2018.2846569"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2418191"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2419658"},{"key":"e_1_2_1_27_1","volume-title":"The movielens datasets: History and context. Acm transactions on interactive intelligent systems (TiiS)","author":"Maxwell Harper F","year":"2015","unstructured":"F Maxwell Harper and Joseph A Konstan . 2015. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (TiiS) , Vol. 5 , 4 ( 2015 ), 1--19. F Maxwell Harper and Joseph A Konstan. 2015. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (TiiS), Vol. 5, 4 (2015), 1--19."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00628-y"},{"key":"e_1_2_1_29_1","volume-title":"Multi-pass streaming algorithms for monotone submodular function maximization. arXiv preprint arXiv:1802.06212","author":"Huang Chien-Chung","year":"2018","unstructured":"Chien-Chung Huang and Naonori Kakimura . 2018. Multi-pass streaming algorithms for monotone submodular function maximization. arXiv preprint arXiv:1802.06212 ( 2018 ). Chien-Chung Huang and Naonori Kakimura. 2018. Multi-pass streaming algorithms for monotone submodular function maximization. arXiv preprint arXiv:1802.06212 (2018)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00786-4"},{"key":"e_1_2_1_31_1","unstructured":"Rishabh K Iyer and Jeff A Bilmes. 2013. Submodular optimization with submodular cover and submodular knapsack constraints. In Advances in Neural Information Processing Systems (NeurIPS). 2436--2444.  Rishabh K Iyer and Jeff A Bilmes. 2013. Submodular optimization with submodular cover and submodular knapsack constraints. In Advances in Neural Information Processing Systems (NeurIPS). 2436--2444."},{"key":"e_1_2_1_32_1","volume-title":"International Conference on Machine Learning (ICML). 3311--3320","author":"Kazemi Ehsan","year":"2019","unstructured":"Ehsan Kazemi , Marko Mitrovic , Morteza Zadimoghaddam , Silvio Lattanzi , and Amin Karbasi . 2019 . Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity . In International Conference on Machine Learning (ICML). 3311--3320 . Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. 2019. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In International Conference on Machine Learning (ICML). 3311--3320."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_34_1","volume-title":"The budgeted maximum coverage problem. Information processing letters (IPL)","author":"Khuller Samir","year":"1999","unstructured":"Samir Khuller , Anna Moss , and Joseph Seffi Naor . 1999. The budgeted maximum coverage problem. Information processing letters (IPL) , Vol. 70 , 1 ( 1999 ), 39--45. Samir Khuller, Anna Moss, and Joseph Seffi Naor. 1999. The budgeted maximum coverage problem. Information processing letters (IPL), Vol. 70, 1 (1999), 39--45."},{"key":"e_1_2_1_35_1","unstructured":"Alex Krizhevsky Geoffrey Hinton etal 2009. Learning multiple layers of features from tiny images. (2009).  Alex Krizhevsky Geoffrey Hinton et al. 2009. Learning multiple layers of features from tiny images. (2009)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0592"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"e_1_2_1_38_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP datasets: Stanford large network dataset collection. https:\/\/snap.stanford.edu\/data\/com-Youtube.html  Jure Leskovec and Andrej Krevl. 2014. SNAP datasets: Stanford large network dataset collection. https:\/\/snap.stanford.edu\/data\/com-Youtube.html"},{"key":"e_1_2_1_39_1","volume-title":"Nearly Linear Time Algorithms and Lower Bound for Submodular Maximization. arXiv e-prints","author":"Li Wenxin","year":"2018","unstructured":"Wenxin Li and Ness Shroff . 2018. Nearly Linear Time Algorithms and Lower Bound for Submodular Maximization. arXiv e-prints ( 2018 ), arXiv--1804. Wenxin Li and Ness Shroff. 2018. Nearly Linear Time Algorithms and Lower Bound for Submodular Maximization. arXiv e-prints (2018), arXiv--1804."},{"key":"e_1_2_1_40_1","volume-title":"Annual Meeting of the Association for Computational Linguistics (ACL). 510--520","author":"Lin Hui","year":"2011","unstructured":"Hui Lin and Jeff Bilmes . 2011 . A class of submodular functions for document summarization . In Annual Meeting of the Association for Computational Linguistics (ACL). 510--520 . Hui Lin and Jeff Bilmes. 2011. A class of submodular functions for document summarization. In Annual Meeting of the Association for Computational Linguistics (ACL). 510--520."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.137"},{"key":"e_1_2_1_42_1","volume-title":"International Conference on Machine Learning (ICML). 1358--1367","author":"Mirzasoleiman Baharan","year":"2016","unstructured":"Baharan Mirzasoleiman , Ashwinkumar Badanidiyuru , and Amin Karbasi . 2016 . Fast constrained submodular maximization: Personalized data summarization . In International Conference on Machine Learning (ICML). 1358--1367 . Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning (ICML). 1358--1367."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11529"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_2_1_45_1","volume-title":"Sample Complexity Bounds for Influence Maximization. In Innovations in Theoretical Computer Science Conference (ITCS).","author":"Sadeh Gal","year":"2020","unstructured":"Gal Sadeh , Edith Cohen , and Haim Kaplan . 2020 . Sample Complexity Bounds for Influence Maximization. In Innovations in Theoretical Computer Science Conference (ITCS). Gal Sadeh, Edith Cohen, and Haim Kaplan. 2020. Sample Complexity Bounds for Influence Maximization. In Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737400"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICNP.2019.8888148"},{"key":"e_1_2_1_48_1","unstructured":"Gamal Sallam Zizhan Zheng Jie Wu and Bo Ji. 2020. Robust Sequence Submodular Maximization. In Advances in Neural Information Processing Systems (NeurIPS).  Gamal Sallam Zizhan Zheng Jie Wu and Bo Ji. 2020. Robust Sequence Submodular Maximization. In Advances in Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2015.2480247"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10653"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3447386","article-title":"Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint","volume":"5","author":"Tang Jing","year":"2021","unstructured":"Jing Tang , Xueyan Tang , Andrew Lim , Kai Han , Chongshou Li , and Junsong Yuan . 2021 . Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint . Proceedings of the ACM on Measurement and Analysis of Computing Systems , Vol. 5 , 1 (2021), 1 -- 22 . Jing Tang, Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, and Junsong Yuan. 2021. Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 5, 1 (2021), 1--22.","journal-title":"Proceedings of the ACM on Measurement and Analysis of Computing Systems"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323679.3326624"},{"key":"e_1_2_1_54_1","volume-title":"International Conference on Artificial Intelligence and Statistics (AISTATS). 3263--3274","author":"Yaroslavtsev Grigory","year":"2020","unstructured":"Grigory Yaroslavtsev , Samson Zhou , and Dmitrii Avdiukhin . 2020 . ?Bring Your Own Greedy\" Max: Near-Optimal 1\/2-Approximations for Submodular Knapsack . In International Conference on Artificial Intelligence and Statistics (AISTATS). 3263--3274 . Grigory Yaroslavtsev, Samson Zhou, and Dmitrii Avdiukhin. 2020. ?Bring Your Own Greedy\" Max: Near-Optimal 1\/2-Approximations for Submodular Knapsack. In International Conference on Artificial Intelligence and Statistics (AISTATS). 3263--3274."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2871668"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33015861"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570615","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:17Z","timestamp":1750178777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1145\/3570615"],"URL":"https:\/\/doi.org\/10.1145\/3570615","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2022-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}