{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T05:57:55Z","timestamp":1733983075917,"version":"3.30.2"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T00:00:00Z","timestamp":1733961600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T00:00:00Z","timestamp":1733961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s11704-024-40266-4","type":"journal-article","created":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T01:43:56Z","timestamp":1733967836000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Deterministic streaming algorithms for non-monotone submodular maximization"],"prefix":"10.1007","volume":"19","author":[{"given":"Xiaoming","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jialin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuo","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,12]]},"reference":[{"key":"40266_CR1","first-page":"137","volume-title":"Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"D Kempe","year":"2003","unstructured":"Kempe D, Kleinberg J, Tardos \u00c9. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, 137\u2013146"},{"key":"40266_CR2","first-page":"45","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"A Das","year":"2008","unstructured":"Das A, Kempe D. Algorithms for subset selection in linear regression. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 45\u201354"},{"key":"40266_CR3","first-page":"1560","volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics","author":"R Khanna","year":"2017","unstructured":"Khanna R, Elenberg E R, Dimakis A G, Negahban S N, Ghosh J. Scalable greedy feature selection via weak submodularity. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. 2017, 1560\u20131568"},{"key":"40266_CR4","first-page":"407","volume-title":"Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence","author":"R Iyer","year":"2012","unstructured":"Iyer R, Bilmes J. Algorithms for approximate minimization of the difference between submodular functions, with applications. In: Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence. 2012, 407\u2013417"},{"key":"40266_CR5","first-page":"2436","volume-title":"Proceedings of the 26th International Conference on Neural Information Processing Systems","author":"R Iyer","year":"2013","unstructured":"Iyer R, Bilmes J. Submodular optimization with submodular cover and submodular knapsack constraints. In: Proceedings of the 26th International Conference on Neural Information Processing Systems. 2013, 2436\u20132444"},{"issue":"1","key":"40266_CR6","doi-asserted-by":"publisher","first-page":"171337","DOI":"10.1007\/s11704-022-2154-x","volume":"17","author":"L B Jin","year":"2023","unstructured":"Jin L B, Zhang L, Zhao L. Max-difference maximization criterion: a feature selection method for text categorization. Frontiers of Computer Science, 2023, 17(1): 171337","journal-title":"Frontiers of Computer Science"},{"issue":"2","key":"40266_CR7","doi-asserted-by":"publisher","first-page":"120101","DOI":"10.1007\/s11432-023-3864-6","volume":"67","author":"J Liang","year":"2024","unstructured":"Liang J, Zhang Y, Chen K, Qu B, Yu K, Yue C, Suganthan P N. An evolutionary multiobjective method based on dominance and decomposition for feature selection in classification. Science China Information Sciences, 2024, 67(2): 120101","journal-title":"Science China Information Sciences"},{"issue":"4","key":"40266_CR8","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/1989734.1989736","volume":"2","author":"A Krause","year":"2011","unstructured":"Krause A, Guestrin C. Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology, 2011, 2(4): 32","journal-title":"ACM Transactions on Intelligent Systems and Technology"},{"issue":"3","key":"40266_CR9","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"G L Nemhauser","year":"1978","unstructured":"Nemhauser G L, Wolsey L A. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 1978, 3(3): 177\u2013188","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"40266_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U. A threshold of ln n for approximating set cover. Journal of the ACM, 1998, 45(4): 634\u2013652","journal-title":"Journal of the ACM"},{"issue":"1","key":"40266_CR11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G L Nemhauser","year":"1978","unstructured":"Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions\u2014I. Mathematical Programming, 1978, 14(1): 265\u2013294","journal-title":"Mathematical Programming"},{"issue":"1","key":"40266_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller S, Moss A, Naor J. The budgeted maximum coverage problem. Information Processing Letters, 1999, 70(1): 39\u201345","journal-title":"Information Processing Letters"},{"issue":"1","key":"40266_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko M. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 2004, 32(1): 41\u201343","journal-title":"Operations Research Letters"},{"key":"40266_CR14","first-page":"67","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"J Vondrak","year":"2008","unstructured":"Vondrak J. Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 67\u201374"},{"key":"40266_CR15","first-page":"545","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A Kulik","year":"2009","unstructured":"Kulik A, Shachnai H, Tamir T. Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. 2009, 545\u2013554"},{"key":"40266_CR16","first-page":"570","volume-title":"Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science","author":"M Feldman","year":"2011","unstructured":"Feldman M, Naor J, Schwartz R. A unified continuous greedy algorithm for submodular maximization. In: Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science. 2011, 570\u2013579"},{"key":"40266_CR17","volume-title":"Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024","author":"N Buchbinder","year":"2024","unstructured":"Buchbinder N, Feldman M. Deterministic algorithm and faster algorithm for submodular maximization subject to a matroid constraint. In: Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024. 2024"},{"key":"40266_CR18","doi-asserted-by":"publisher","first-page":"1820","DOI":"10.1145\/3618260.3649630","volume-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing","author":"N Buchbinder","year":"2024","unstructured":"Buchbinder N, Feldman M. Constrained submodular maximization via new bounds for DR-submodular functions. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024, 1820\u20131831"},{"issue":"3","key":"40266_CR19","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/3184990","volume":"14","author":"N Buchbinder","year":"2018","unstructured":"Buchbinder N, Feldman M. Deterministic algorithms for submodular maximization problems. ACM Transactions on Algorithms, 2018, 14(3): 32","journal-title":"ACM Transactions on Algorithms"},{"key":"40266_CR20","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1007\/978-3-031-22105-7_44","volume-title":"Proceedings of Computing and Combinatorics: 28th International Conference","author":"X Sun","year":"2022","unstructured":"Sun X, Zhang J, Zhang S, Zhang Z. Improved deterministic algorithms for non-monotone submodular maximization. In: Proceedings of Computing and Combinatorics: 28th International Conference. 2022, 496\u2013507"},{"key":"40266_CR21","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1145\/2623330.2623637","volume-title":"Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"A Badanidiyuru","year":"2014","unstructured":"Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A. Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2014, 671\u2013680"},{"key":"40266_CR22","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1145\/3357713.3384286","volume-title":"Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing","author":"M Feldman","year":"2020","unstructured":"Feldman M, Norouzi-Fard A, Svensson O, Zenklusen R. The one-way communication complexity of submodular maximization with applications to streaming and robustness. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 2020, 1363\u20131374"},{"issue":"4","key":"40266_CR23","doi-asserted-by":"publisher","first-page":"2667","DOI":"10.1287\/moor.2021.1224","volume":"47","author":"N Alaluf","year":"2022","unstructured":"Alaluf N, Ene A, Feldman M, Nguyen H L, Suh A. An optimal streaming algorithm for submodular maximization with a cardinality constraint. Mathematics of Operations Research, 2022, 47(4): 2667\u20132690","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"40266_CR24","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1007\/s00453-019-00628-y","volume":"82","author":"C C Huang","year":"2020","unstructured":"Huang C C, Kakimura N, Yoshida Y. Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica, 2020, 82(4): 1006\u20131032","journal-title":"Algorithmica"},{"issue":"3","key":"40266_CR25","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1007\/s00453-020-00786-4","volume":"83","author":"C C Huang","year":"2021","unstructured":"Huang C C, Kakimura N. Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica, 2021, 83(3): 879\u2013902","journal-title":"Algorithmica"},{"issue":"1","key":"40266_CR26","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/s00224-021-10065-6","volume":"66","author":"C C Huang","year":"2022","unstructured":"Huang C C, Kakimura N. Multi-pass streaming algorithms for monotone submodular function maximization. Theory of Computing Systems, 2022, 66(1): 354\u2013394","journal-title":"Theory of Computing Systems"},{"key":"40266_CR27","first-page":"3263","volume-title":"Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics","author":"G Yaroslavtsev","year":"2020","unstructured":"Yaroslavtsev G, Zhou S, Avdiukhin D. \u201cBring your own greedy\u201d+max: near-optimal 1\/2-approximations for submodular knapsack. In: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics. 2020, 3263\u20133274"},{"issue":"3","key":"40266_CR28","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/2809814","volume":"2","author":"R Kumar","year":"2015","unstructured":"Kumar R, Moseley B, Vassilvitskii S, Vattani A. Fast greedy algorithms in mapReduce and streaming. ACM Transactions on Parallel Computing, 2015, 2(3): 14","journal-title":"ACM Transactions on Parallel Computing"},{"key":"40266_CR29","first-page":"1295","volume-title":"Proceedings of 2016 IEEE Global Conference on Signal and Information Processing","author":"Q Yu","year":"2016","unstructured":"Yu Q, Xu E L, Cui S. Submodular maximization with multi-knapsack constraints and its applications in scientific literature recommendations. In: Proceedings of 2016 IEEE Global Conference on Signal and Information Processing. 2016, 1295\u20131299"},{"key":"40266_CR30","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-17572-5_20","volume-title":"Proceedings of the 6th International Workshop on Internet and Network Economics","author":"A Gupta","year":"2010","unstructured":"Gupta A, Roth A, Schoenebeck G, Talwar K. Constrained nonmonotone submodular maximization: offline and secretary algorithms. In: Proceedings of the 6th International Workshop on Internet and Network Economics. 2010, 246\u2013257"},{"issue":"4","key":"40266_CR31","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1137\/090750020","volume":"23","author":"J Lee","year":"2010","unstructured":"Lee J, Mirrokni V S, Nagarajan V, Sviridenko M. Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM Journal on Discrete Mathematics, 2010, 23(4): 2053\u20132078","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"6","key":"40266_CR32","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/j.orl.2011.10.002","volume":"39","author":"S Fadaei","year":"2011","unstructured":"Fadaei S, Fazli M A, Safari M A. Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms. Operations Research Letters, 2011, 39(6): 447\u2013451","journal-title":"Operations Research Letters"},{"issue":"3","key":"40266_CR33","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1287\/moor.2018.0955","volume":"44","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder N, Feldman M. Constrained submodular maximization via a nonsymmetric technique. Mathematics of Operations Research, 2019, 44(3): 988\u20131005","journal-title":"Mathematics of Operations Research"},{"key":"40266_CR34","doi-asserted-by":"publisher","first-page":"114293","DOI":"10.1016\/j.tcs.2023.114293","volume":"984","author":"X Sun","year":"2024","unstructured":"Sun X, Zhang J, Zhang S, Zhang Z. Improved deterministic algorithms for non-monotone submodular maximization. Theoretical Computer Science, 2024, 984: 114293","journal-title":"Theoretical Computer Science"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-024-40266-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-024-40266-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-024-40266-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T02:07:44Z","timestamp":1733969264000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-024-40266-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,12]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["40266"],"URL":"https:\/\/doi.org\/10.1007\/s11704-024-40266-4","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,12]]},"assertion":[{"value":"25 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"<b>Competing interests<\/b> Xiaoming Sun is an Editorial Board member of the journal and a co-author of this article. To minimize bias, they were excluded from all editorial decision-making related to the acceptance of this article for publication. The remaining authors declare no conflict of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics"}}],"article-number":"196404"}}