{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:46Z","timestamp":1740122386462,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T00:00:00Z","timestamp":1669075200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T00:00:00Z","timestamp":1669075200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971447","11871442"],"award-info":[{"award-number":["11971447","11871442"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2020MA045"],"award-info":[{"award-number":["ZR2020MA045"]}],"id":[{"id":"10.13039\/501100007129","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":[[2023,1]]},"DOI":"10.1007\/s10878-022-00951-1","type":"journal-article","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T11:08:20Z","timestamp":1673953700000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Streaming submodular maximization under d-knapsack constraints"],"prefix":"10.1007","volume":"45","author":[{"given":"Zihan","family":"Chen","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8958-3999","authenticated-orcid":false,"given":"Bin","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Hongmin W.","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,22]]},"reference":[{"issue":"6","key":"951_CR1","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(516)","volume":"134","author":"A Krause","year":"2008","unstructured":"Krause A, Leskovec J, Guestrin C, VanBriesen J, Faloutsos C (2008) Efficient sensor placement optimization for securing large water distribution networks. J Water Resour Plan Manag 134(6):516\u2013526","journal-title":"J Water Resour Plan Manag"},{"doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: massive data summarization on the fly. In: 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 671\u2013680. Association for Computing Machinery, New York, NY, USA","key":"951_CR2","DOI":"10.1145\/2623330.2623637"},{"doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Schwartz R : Online submodular maximization with preemption. In: 26th ACM-SIAM symposium on Discrete algorithms, pp. 1202\u20131216. Society for Industrial and Applied Mathematics, Cambridge, Massachusetts, USA (2014)","key":"951_CR3","DOI":"10.1137\/1.9781611973730.80"},{"unstructured":"Calinescu G, Chekuri C, Pal M, Vondrak J : Maximizing a submodular function subject to a matroid constraint. In: 12th International Conference on Integer Programming and Combinatorial Optimization. (2007)","key":"951_CR4"},{"doi-asserted-by":"crossref","unstructured":"Chen W, Wang C, Wang Y : Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1029-1038. (2010)","key":"951_CR5","DOI":"10.1145\/1835804.1835934"},{"doi-asserted-by":"crossref","unstructured":"Kempe David, Kleinberg Jon, and Tardos \u00c9va : Maximizing the spread of influence through a social network. In: 9th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137\u2013146. Association for Computing Machinery, Washington, DC, USA (2003)","key":"951_CR6","DOI":"10.1145\/956750.956769"},{"unstructured":"Fujishige S : Submodular functions and optimization. Elsevier. (2005)","key":"951_CR7"},{"issue":"4","key":"951_CR8","doi-asserted-by":"publisher","first-page":"2775","DOI":"10.1109\/TNSE.2020.2993042","volume":"7","author":"J Guo","year":"2020","unstructured":"Guo J, Chen T, Wu W (2020) Continuous activity maximization in online social networks. IEEE Trans Netw Sc Eng 7(4):2775\u20132786","journal-title":"IEEE Trans Netw Sc Eng"},{"issue":"3","key":"951_CR9","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1109\/TCSS.2021.3061452","volume":"8","author":"J Guo","year":"2021","unstructured":"Guo J, Wu W (2021) Continuous profit maximization: a study of unconstrained dr-submodular maximization. IEEE Trans Comput Soc Syst 8(3):768\u2013779","journal-title":"IEEE Trans Comput Soc Syst"},{"issue":"5","key":"951_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3447396","volume":"15","author":"J Guo","year":"2021","unstructured":"Guo J, Wu W (2021) Adaptive influence maximization: if influential node unwilling to be the seed. ACM Trans Knowl Discov Data 15(5):1\u201323","journal-title":"ACM Trans Knowl Discov Data"},{"unstructured":"Horel T, Singer Y (2016) Maximization of approximately submodular functions. In: Annual conference on neural information processing systems, pp 3045\u20133053. Barcelona, Spain","key":"951_CR11"},{"unstructured":"Hassidim A, Singer Y (2017) Submodular optimization under noise. In: 2017 Conference on learning theory, pp. 1069\u20131122. PMLR","key":"951_CR12"},{"issue":"3","key":"951_CR13","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1007\/s00453-020-00786-4","volume":"83","author":"C Huang","year":"2021","unstructured":"Huang C, Kakimura N (2021) Improved streaming algorithms for maximising monotone submodular functions under a knapsack constraint. Algorithmica 83(3):879\u2013902","journal-title":"Algorithmica"},{"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: 36th International conference on machine learning, pp. 3311\u20133320. International Machine Learning Society, Long Beach, California","key":"951_CR14"},{"unstructured":"Mitrovic M, Kazemi E, Zadimoghaddam M, Karbasi A (2018) Data summarization at scale: A two-stage submodular approach. In: 35th International conference on machine learning, PMLR pp 3596\u20133605","key":"951_CR15"},{"doi-asserted-by":"crossref","unstructured":"Kapralov M, Post I et al (2013) Online submodular welfare maximization: greedy is optimal. In: 24th ACM-SIAM Symposium on Discrete Algorithms, pp 1216\u20131225. Society for Industrial and Applied Mathematics, New Orleans, Louisiana, USA","key":"951_CR16","DOI":"10.1137\/1.9781611973105.88"},{"doi-asserted-by":"crossref","unstructured":"Kulik A, Shachnai H, Tamir T (2009) Maximizing submodular set functions subject to multiple linear constraints. In: 20th ACM-SIAM symposium on discrete algorithms, pp 545\u2013554. Society for Industrial and Applied Mathematics","key":"951_CR17","DOI":"10.1137\/1.9781611973068.60"},{"doi-asserted-by":"crossref","unstructured":"Leskovec J, Krause A, Guestrin C, et al (2007) Cost-effective outbreak detection in networks. In: 13th ACM SIGKDD international conference on Knowledge discovery and data mining. pp 420\u2013429. Association for Computing Machinery, New York, NY, United States","key":"951_CR18","DOI":"10.1145\/1281192.1281239"},{"unstructured":"Lin H, Bilmes J (2010) Multi-document summarization via budgeted maximization of submodular functions. In: Human Language Technologies: The 2010 Annual conference of the North American chapter of the association for computational linguistics, pp 912\u2013920. Association for Computational Linguistics, Los Angeles, California","key":"951_CR19"},{"issue":"1","key":"951_CR20","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/BF02680565","volume":"83","author":"K Murota","year":"1998","unstructured":"Murota K (1998) Discrete convex analysis. Math Program 83(1):313\u2013371","journal-title":"Math Program"},{"unstructured":"Norouzi-Fard A, Tarnawski J, Mitrovic S, Zandieh A, Mousavifar A, Svensson O (2018) Beyond 1\/2-approximation for submodular maximization on massive data streams. In: 35th International conference on machine learning, pp 3829\u20133838. International Machine Learning Society, Stockholm, Sweden","key":"951_CR21"},{"issue":"1","key":"951_CR22","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"L Nemhauser","year":"1978","unstructured":"Nemhauser L, Wolsey A, Fisher L (1978) An analysis of approximations for maximizing submodular set functions-I. Math Program 14(1):265\u2013294","journal-title":"Math Program"},{"issue":"3","key":"951_CR23","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"L Nemhauser","year":"1978","unstructured":"Nemhauser L, Wolsey A (1978) Best algorithms for approximating the maximum of a submodular set function. Math Oper Res 3(3):177\u2013188","journal-title":"Math Oper Res"},{"unstructured":"Qian C, Shi JC, Yu Y, Tang K, Zhou ZH (2017) Subset selection under noise. In: NIPS, pp 3560\u20133570","key":"951_CR24"},{"unstructured":"Soma T, Kakimura N, Inaba K, Kawarabayashi K-I (2014) Optimal budget allocation: Theoretical guarantee and efficient algorithm. In: 31th International conference on machine learning, pp 351\u2013359. International Machine Learning Society, Beijing, China","key":"951_CR25"},{"issue":"1","key":"951_CR26","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s10107-018-1324-y","volume":"172","author":"T Soma","year":"2018","unstructured":"Soma T, Yoshida Y (2018) Maximizing monotone submodular functions over the integer lattice. Math Program 172(1):539\u2013563","journal-title":"Math Program"},{"issue":"1","key":"951_CR27","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"},{"issue":"7","key":"951_CR28","doi-asserted-by":"publisher","first-page":"1327","DOI":"10.1109\/TKDE.2018.2854182","volume":"31","author":"Y Wang","year":"2018","unstructured":"Wang Y, Li Y, Tan KL (2018) Efficient representative subset selection over sliding windows. IEEE Trans Knowl Data Eng 31(7):1327\u20131340","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"3","key":"951_CR29","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"L Wolsey","year":"1982","unstructured":"Wolsey L (1982) Maximising real-valued submodular set function: primal and dual heuristics for location problems. Math Oper Res 7(3):410\u2013425","journal-title":"Math Oper Res"},{"key":"951_CR30","doi-asserted-by":"publisher","first-page":"53736","DOI":"10.1109\/ACCESS.2018.2871668","volume":"6","author":"Q Yu","year":"2018","unstructured":"Yu Q, Xu L, Cui S (2018) Streaming algorithms for news and scientific literature recommendation: monotone submodular maximization with a d-Knapsack constraint. IEEE Access 6:53736\u201353747","journal-title":"IEEE Access"},{"doi-asserted-by":"crossref","unstructured":"Yang R, Xu D, Cheng Y, Gao C, Du DZ (2019) Streaming submodular maximization under noises. In: 39th International conference on distributed computing systems (ICDCS), pp 348\u2013357","key":"951_CR31","DOI":"10.1109\/ICDCS.2019.00042"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00951-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00951-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00951-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T07:52:56Z","timestamp":1675497176000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00951-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,22]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["951"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00951-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,11,22]]},"assertion":[{"value":"20 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"There are no conflicts of interest or competing interests for this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"15"}}