{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T11:14:12Z","timestamp":1772882052357,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,10,26]],"date-time":"2020-10-26T00:00:00Z","timestamp":1603670400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,26]],"date-time":"2020-10-26T00:00:00Z","timestamp":1603670400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11531014"],"award-info":[{"award-number":["11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61772005"],"award-info":[{"award-number":["61772005"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"publisher","award":["2017J01753"],"award-info":[{"award-number":["2017J01753"]}],"id":[{"id":"10.13039\/501100003392","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s10878-020-00662-5","type":"journal-article","created":{"date-parts":[[2020,10,26]],"date-time":"2020-10-26T07:02:36Z","timestamp":1603695756000},"page":"43-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Sequence submodular maximization meets streaming"],"prefix":"10.1007","volume":"41","author":[{"given":"Ruiqi","family":"Yang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2891-4253","authenticated-orcid":false,"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,26]]},"reference":[{"key":"662_CR1","unstructured":"Alaluf N, Feldman M (2019) Making a sieve random: Improved semi-streaming algorithm for submodular maximization under a cardinality constraint. ArXiv: 1906.11237"},{"key":"662_CR2","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining, pp 671\u2013680","DOI":"10.1145\/2623330.2623637"},{"key":"662_CR3","unstructured":"Bai W, Bilmes J (2018) Greed is still good: Maximizing monotone submodular $$+$$ supermodular(BP) functions. In Proceedings of the 35th international conference on machine learning, pp 314\u2013323"},{"key":"662_CR4","unstructured":"Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017) Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th international conference on machine learning, pp 498\u2013507"},{"key":"662_CR5","unstructured":"Bogunovic I, Zhao J, Cevher V (2018) Robust maximization of non-submodular objectives. In Proceedings of the 21st international conference on artificial intelligence and statistics, pp 890\u2013899"},{"key":"662_CR6","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Garg M (2019) Deterministic $$(1\/2+\\epsilon )$$-approximation for submodular maximization over a matroid. In Proceedings of the 30th Annual ACM-SIAM symposium on discrete algorithms, pp 241\u2013254","DOI":"10.1137\/1.9781611975482.16"},{"key":"662_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Naor JS, Schwartz R (2014) Submodular maximization with cardinality constraints. In Proceedings of the 25th Annual ACM-SIAM symposium on discrete algorithms, pp 1433\u20131452","DOI":"10.1137\/1.9781611973730.80"},{"issue":"5","key":"662_CR8","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/130929205","volume":"44","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder N, Feldman M, Seffi J, Schwartz R (2015) A tight linear time $$(1\/2)$$-approximation for unconstrained submodular maximization. SIAM J Comput 44(5):1384\u20131402","journal-title":"SIAM J Comput"},{"issue":"6","key":"662_CR9","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu G, Chekuri C, Pal M, Vondr\u00e1k J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J Comput 40(6):1740\u20131766","journal-title":"SIAM J Comput"},{"issue":"1\u20132","key":"662_CR10","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 (2015) Submodular maximization meets streaming: Matchings, matroids, and more. Math Program 154(1\u20132):225\u2013247","journal-title":"Math Program"},{"key":"662_CR11","doi-asserted-by":"crossref","unstructured":"Chekuri C, Gupta S, Quanrud K (2015) Streaming algorithms for submodular function maximization. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, pp 318\u2013330","DOI":"10.1007\/978-3-662-47672-7_26"},{"issue":"3","key":"662_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti M, Cornu\u00e9jols G (1984) Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl Math 7(3):251\u2013274","journal-title":"Discrete Appl Math"},{"key":"662_CR13","unstructured":"Das A, Kempe D (2011) Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th international conference on machine learning, pp 1057\u20131064"},{"issue":"3","key":"662_CR14","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s40305-014-0053-z","volume":"2","author":"D Du","year":"2014","unstructured":"Du D, Li Y, Xiu N, Xu D (2014) Simultaneous approximation of multi-criteria submodular function maximization. J Oper Res Soc China 2(3):271\u2013290","journal-title":"J Oper Res Soc China"},{"key":"662_CR15","unstructured":"Elenberg ER, Dimakis AG, Feldman M, Karbasi A (2017) Streaming weak submodularity: Interpreting neural networks on the fly. In Proceedings of the 31st international conference on neural information processing systems, pp 4044\u20134054"},{"key":"662_CR16","doi-asserted-by":"crossref","unstructured":"Ene A, Nguyen HL (2016) Constrained submodular maximization: Beyond $$1\/e$$. In Proceedings of the 57th IEEE annual symposium on foundations of computer science, pp 248\u2013257","DOI":"10.1109\/FOCS.2016.34"},{"key":"662_CR17","unstructured":"Ene A, Nguyen HL, Suh A (2019) An optimal streaming algorithm for non-monotone submodular Maximization. ArXiv:1911.12959"},{"issue":"4","key":"662_CR18","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of $$\\ln n$$ for approximating set cover. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"key":"662_CR19","doi-asserted-by":"crossref","unstructured":"Feige U, Izsak R (2013) Welfare maximization and the supermodular degree. In Proceedings of the 4th conference on innovations in theoretical computer science, pp 247-256","DOI":"10.1145\/2422436.2422466"},{"issue":"4","key":"662_CR20","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige U, Mirrokni VS, Vondr\u00e1k J (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133\u20131153","journal-title":"SIAM J Comput"},{"key":"662_CR21","unstructured":"Feldman M, Karbasi A, Kazemi E (2018) Do less, get more: Streaming submodular maximization with subsampling. In Proceedings of the 32nd international conference on neural information processing systems, pp 730\u2013740"},{"key":"662_CR22","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. In Proceedings of the 52nd IEEE annual symposium on foundations of computer science, pp 570\u2013579","DOI":"10.1109\/FOCS.2011.46"},{"key":"662_CR23","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor JS, Schwartz R (2011) Nonmonotone submodular maximization via a structural continuous greedy algorithm. In Proceedings of the 38th international colloquium on automata, languages, and programming, pp 342\u2013353","DOI":"10.1007\/978-3-642-22006-7_29"},{"key":"662_CR24","doi-asserted-by":"crossref","unstructured":"Filmus Y, Ward J (2012) A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In Proceedings of the 53rd Annual IEEE symposium on foundations of computer science, pp 659\u2013668","DOI":"10.1109\/FOCS.2012.55"},{"key":"662_CR25","doi-asserted-by":"crossref","unstructured":"Gharan SO, Vondr\u00e1k J (2011) Submodular maximization by simulated annealing. In Proceedings of the 22nd Annual ACM-SIAM symposium on discrete algorithms, pp 1098\u20131116","DOI":"10.1137\/1.9781611973082.83"},{"issue":"1","key":"662_CR26","first-page":"427","volume":"42","author":"D Golovin","year":"2011","unstructured":"Golovin D, Krause A (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. J Artif Intell Res 42(1):427\u2013486","journal-title":"J Artif Intell Res"},{"key":"662_CR27","doi-asserted-by":"crossref","unstructured":"Gupta A, Roth A, Schoenebeck G, Talwar K (2010) Constrained non-monotone submodular maximization: offline and secretary algorithms. In Proceedings of the 6th international conference on internet and network economics, pp 246\u2013257","DOI":"10.1007\/978-3-642-17572-5_20"},{"key":"662_CR28","unstructured":"Haba R, Kazemi E, Feldman F, Karbasi A (2020) Streaming submodular maximization under a $$k$$-set system constraint. ArXiv: 2002.03352"},{"key":"662_CR29","unstructured":"Huang CC, Kakimura N, Yoshida Y (2017) Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. In Proceedings of the 20th international workshop on approximation algorithms for combinatorial optimization problems and the 21st international workshop on randomization and computation No. 11, 11:1\u201311:14"},{"key":"662_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-019-01430-z","author":"Y Jiang","year":"2019","unstructured":"Jiang Y, Wang Y, Xu D, Yang R, Zhang Y (2019) Streaming algorithm for maximizing a monotone non-submodular function under $$d$$-knapsack constraint. Optim Lett. https:\/\/doi.org\/10.1007\/s11590-019-01430-z","journal-title":"Optim Lett"},{"key":"662_CR31","unstructured":"Kazemi E, Mitrovic M, Zadimoghaddam M, Lattanzi S, Karbasi A (2019) Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In Proceedings of the 36th international conference on machine learning, pp 3311\u20133320"},{"issue":"4","key":"662_CR32","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1137\/090750020","volume":"23","author":"J Lee","year":"2010","unstructured":"Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2010) Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J Discrete Math 23(4):2053\u20132078","journal-title":"SIAM J Discrete Math"},{"key":"662_CR33","unstructured":"Mitrovic M, Feldman M, Krause A, Karbasi A (2018) Submodularity on hypergraphs: From sets to sequences. In Proceedings of the 21st international conference on artificial intelligence and statistics, pp 1177\u20131184"},{"key":"662_CR34","unstructured":"Mitrovic M, Kazemi E, Feldman M, Krause A, Karbasi A (2019) Adaptive sequence submodularity. ArXiv:1902.05981"},{"issue":"1","key":"662_CR35","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions-I. Math Program 14(1):265\u2013294","journal-title":"Math Program"},{"key":"662_CR36","unstructured":"Norouzi-Fard A, Tarnawski J, Mitrovi\u0107 S, Zandieh A, Mousavifar A, Svensson O (2018) Beyond $$1\/2$$-approximation for submodular maximization on massive data streams. In Proceedings of the 35th international conference on machine learning, pp 3826\u20133835"},{"issue":"1","key":"662_CR37","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 (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 32(1):41\u201343","journal-title":"Oper Res Lett"},{"key":"662_CR38","doi-asserted-by":"crossref","unstructured":"Sviridenko M, Vondr\u00e1k J, Ward J (2015) Optimal approximation for submodular and supermodular optimization with bounded curvature. In: Proceedings of the 26th Annual ACM-SIAM symposium on discrete algorithms, pp 1134\u20131148","DOI":"10.1137\/1.9781611973730.76"},{"key":"662_CR39","doi-asserted-by":"crossref","unstructured":"Tschiatschek S, Singla A, Krause A (2017) Selecting sequences of items via submodular maximization. In: Proceedings of the 31st AAAI conference on artificial intelligence, pp 2667\u20132673","DOI":"10.24963\/ijcai.2018\/379"},{"issue":"1","key":"662_CR40","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10878-014-9707-3","volume":"31","author":"Z Wang","year":"2016","unstructured":"Wang Z, Moran B, Wang X, Pan Q (2016) Approximation for maximizing monotone non-decreasing set functions with a greedy method. J Comb Optim 31(1):29\u201343","journal-title":"J Comb Optim"},{"issue":"3","key":"662_CR41","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s40305-019-00244-1","volume":"7","author":"Y Wang","year":"2019","unstructured":"Wang Y, Xu D, Jiang Y, Zhang D (2019) Minimizing ratio of monotone non-submodular functions. J Oper Res Soc China 7(3):449\u2013459","journal-title":"J Oper Res Soc China"},{"issue":"4","key":"662_CR42","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/s10898-019-00840-8","volume":"76","author":"Y Wang","year":"2020","unstructured":"Wang Y, Xu D, Wang Y, Zhang D (2020) Non-submodular maximization on massive data streams. J Glob Optim 76(4):729\u2013743","journal-title":"J Glob Optim"},{"issue":"2","key":"662_CR43","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s40305-018-0233-3","volume":"7","author":"W Wu","year":"2019","unstructured":"Wu W, Zhang Z, Du D (2019) Set function optimization. J Oper Res Soc China 7(2):183\u2013193","journal-title":"J Oper Res Soc China"},{"key":"662_CR44","doi-asserted-by":"crossref","unstructured":"Yang R, Xu D, Du D, Xu Y, Yan X (2019) Maximization of constrained non-submodular functions. In: Proceedings of the 25th international computing and combinatorics conference, pp 615\u2013626","DOI":"10.1007\/978-3-030-26176-4_51"},{"key":"662_CR45","doi-asserted-by":"crossref","unstructured":"Yang R, Xu D, Guo L, Zhang D (2019) Sequence submodular maximization meets streaming. In: Proceedings of the 13th international conference on combinatorial optimization and applications, pp 565\u2013575","DOI":"10.1007\/978-3-030-36412-0_46"},{"issue":"4","key":"662_CR46","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1142\/S0217595919500222","volume":"36","author":"R Yang","year":"2019","unstructured":"Yang R, Xu D, Jiang Y, Wang Y, Zhang D (2019) Approximating robust parameterized submodular function maximization in large-scales. Asia-Pac J Oper Res 36(4):671\u2013680","journal-title":"Asia-Pac J Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00662-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00662-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00662-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T00:38:34Z","timestamp":1635208714000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00662-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,26]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["662"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00662-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,26]]},"assertion":[{"value":"14 October 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}