{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T01:44:25Z","timestamp":1778550265306,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T00:00:00Z","timestamp":1557100800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T00:00:00Z","timestamp":1557100800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11801251"],"award-info":[{"award-number":["11801251"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61433012"],"award-info":[{"award-number":["61433012"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61433012"],"award-info":[{"award-number":["61433012"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1435215"],"award-info":[{"award-number":["U1435215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1435215"],"award-info":[{"award-number":["U1435215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11531014"],"award-info":[{"award-number":["11531014"]}],"id":[{"id":"10.13039\/501100001809","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":["Optim Lett"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s11590-019-01430-z","type":"journal-article","created":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T16:36:04Z","timestamp":1557160564000},"page":"1235-1248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Streaming algorithm for maximizing a monotone non-submodular function under d-knapsack constraint"],"prefix":"10.1007","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0842-8533","authenticated-orcid":false,"given":"Yanjun","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishui","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruiqi","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,6]]},"reference":[{"issue":"2","key":"1430_CR1","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"4","key":"1430_CR2","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761\u2013777 (2001)","journal-title":"J. ACM"},{"issue":"2\u20133","key":"1430_CR3","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00103-1","volume":"93","author":"AA Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.I.: An 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Appl. Math. 93(2\u20133), 149\u2013156 (1999)","journal-title":"Discrete Appl. Math."},{"key":"1430_CR4","doi-asserted-by":"crossref","unstructured":"Anstreicher, K.M., Lee, J.: A Masked Spectral Bound For Maximum-entropy Sampling. mODa 7-Advances in Model-Oriented Design and Analysis. Physica, Heidelberg, pp. 1\u201312 (2004)","DOI":"10.1007\/978-3-7908-2693-7_1"},{"key":"1430_CR5","unstructured":"Feige, U., Goemans, M.: Approximating the value of two prover proof systems, with applications to max 2sat and max dicut. In: Proceedings of 3th Israel Symposium on Theory of Computing and Systems, pp. 182\u2013189 (1995)"},{"issue":"1\u20132","key":"1430_CR6","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-009-0298-1","volume":"128","author":"S Ahmed","year":"2011","unstructured":"Ahmed, S., Atamtrk, A.: Maximizing a class of submodular utility functions. Math. Program. 128(1\u20132), 149\u2013169 (2011)","journal-title":"Math. Program."},{"key":"1430_CR7","doi-asserted-by":"crossref","unstructured":"Hartline, J., Mirrokni, V., Sundararajan, M.: Optimal marketing strategies over social networks. In: Proceedings of the 17th International Conference on World Wide Web, pp. 189\u2013198 (2008)","DOI":"10.1145\/1367497.1367524"},{"issue":"2","key":"1430_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.disopt.2013.02.002","volume":"10","author":"AS Schulz","year":"2013","unstructured":"Schulz, A.S., Uhan, N.A.: Approximating the least core value and least core of cooperative games with supermodular costs. Discrete Optim. 10(2), 163\u2013180 (2013)","journal-title":"Discrete Optim."},{"issue":"1","key":"1430_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions\u2014I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"1","key":"1430_CR10","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. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"1430_CR11","doi-asserted-by":"crossref","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular functions subject to multiple linear constraints. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 545\u2013554 (2009)","DOI":"10.1137\/1.9781611973068.60"},{"issue":"4","key":"1430_CR12","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 J. Discrete Math. 23(4), 2053\u20132078 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"1430_CR13","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Peng, R., Tangwongsan, K.: Linear-work greedy parallel approximate set cover and variants. In: Proceedings of the 23th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 23\u201332 (2011)","DOI":"10.1145\/1989493.1989497"},{"key":"1430_CR14","doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Kumar, R., Tomkins, A.: Max-cover in map-reduce. In: Proceedings of the 19th International Conference on World Wide Web, pp. 231\u2013240 (2010)","DOI":"10.1145\/1772690.1772715"},{"key":"1430_CR15","doi-asserted-by":"crossref","unstructured":"Cormode, G., Karloff, H.J., Wirth, A.: Set cover algorithms for very large datasets. In: Proceedings of the 19th ACM Conference on Information and Knowledge Management, pp. 479\u2013488 (2010)","DOI":"10.1145\/1871437.1871501"},{"key":"1430_CR16","unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 1, 510\u2013520 (2011)"},{"key":"1430_CR17","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A.: Fast constrained submodular maximization: personalized data summarization. In: Proceedings of the 33rd International Conference on Machine Learning, 48, 1358\u20131366 (2016)"},{"key":"1430_CR18","doi-asserted-by":"crossref","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, pp. 671\u2013680 (2014)","DOI":"10.1145\/2623330.2623637"},{"key":"1430_CR19","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.: Streaming algorithms for news and scientific literature recommendation: monotone submodular maximization with a $$d$$-Knapsack constraint. IEEE Access 6, 53736\u201353747 (2018)","journal-title":"IEEE Access"},{"key":"1430_CR20","doi-asserted-by":"publisher","unstructured":"Wang, Y., Li, Y., Tan, K.L.: Efficient representative subset selection over sliding windows. IEEE Trans. Knowl. Data Eng. (2018) \nhttps:\/\/doi.org\/10.1109\/TKDE.2018.2854182","DOI":"10.1109\/TKDE.2018.2854182"},{"key":"1430_CR21","unstructured":"Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. (2017). arXiv preprint \narXiv: 1703.02100"},{"key":"1430_CR22","unstructured":"Kuhnle, A., Smith, J. D., Crawford, V. G., Thai, M. T.: Fast maximization of non-submodular, monotonic functions on the integer lattice. (2018). arXiv preprint \narXiv: 1805.06990"},{"key":"1430_CR23","unstructured":"Das, A., Kempe, D.: 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 (2011)"},{"key":"1430_CR24","unstructured":"Khanna, R., Elenberg, E., Dimakis, A. G., Negahban, S., Ghosh, J.: Scalable greedy feature selection via weak submodularity. (2017) arXiv preprint \narXiv: 1703.02723"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-019-01430-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-019-01430-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-019-01430-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T12:06:31Z","timestamp":1592654791000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-019-01430-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,6]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["1430"],"URL":"https:\/\/doi.org\/10.1007\/s11590-019-01430-z","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,6]]},"assertion":[{"value":"9 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}