{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T01:44:22Z","timestamp":1778550262108,"version":"3.51.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,10,16]],"date-time":"2019-10-16T00:00:00Z","timestamp":1571184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,16]],"date-time":"2019-10-16T00:00:00Z","timestamp":1571184000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"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":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61433012"],"award-info":[{"award-number":["61433012"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U1435215"],"award-info":[{"award-number":["U1435215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s10898-019-00840-8","type":"journal-article","created":{"date-parts":[[2019,10,16]],"date-time":"2019-10-16T12:18:47Z","timestamp":1571228327000},"page":"729-743","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Non-submodular maximization on massive data streams"],"prefix":"10.1007","volume":"76","author":[{"given":"Yijing","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishui","family":"Wang","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":[[2019,10,16]]},"reference":[{"key":"840_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Gollapudi, S., Halverson, A., Ieong, S.: Diversifying search results. In: Proceedings of WSDM, pp. 5\u201314 (2009)","DOI":"10.1145\/1498759.1498766"},{"key":"840_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Jayram, T.S., Kumar, R., Sivakumar, D.: Approximate counting of inversions in a data stream. In: Proceedings of STOC, pp. 370\u2013379 (2002)","DOI":"10.1145\/509907.509964"},{"key":"840_CR3","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 SIGKDD, pp. 671\u2013680 (2014)","DOI":"10.1145\/2623330.2623637"},{"key":"840_CR4","unstructured":"Barbosa, R., Ene, A., Nguyen, H.L., Ward, J.: The power of randomization: distributed submodular maximization on massive datasets. In: Proceedings of ICML, pp. 1236\u20131244 (2015)"},{"key":"840_CR5","unstructured":"Barbosa, R., Ene, A., Nguyen, H.L., Ward, J.: A new framework for distributed submodular maximization. In: Proceedings of FOCS, pp. 645\u2013654 (2016)"},{"key":"840_CR6","unstructured":"Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of ICML, pp. 498\u2013507 (2017)"},{"key":"840_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Online submodular maximization with preemption. In: Proceedings of SODA, pp. 1202\u20131216 (2015)","DOI":"10.1137\/1.9781611973730.80"},{"key":"840_CR8","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.: Submodular maximization meets streaming: matchings, matroids, and more. Math. Program. 154, 225\u2013247 (2015)","journal-title":"Math. Program."},{"key":"840_CR9","unstructured":"Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of ICML, pp. 1057\u20131064 (2011)"},{"key":"840_CR10","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s40305-014-0053-z","volume":"2","author":"DL Du","year":"2014","unstructured":"Du, D.L., Li, Y., Xiu, N.H., Xu, D.C.: Simultaneous approximation of multi-criteria submodular function maximization. J. Oper. Res. Soc. China 2, 271\u2013290 (2014)","journal-title":"J. Oper. Res. Soc. China"},{"key":"840_CR11","doi-asserted-by":"crossref","unstructured":"Dueck, D., Frey, B.J.: Non-metric affinity propagation for unsupervised image categorization. In: Proceedings of ICCV, pp. 1\u20138 (2007)","DOI":"10.1109\/ICCV.2007.4408853"},{"key":"840_CR12","doi-asserted-by":"crossref","unstructured":"El-Arini, K., Guestrin, C.: Beyond keyword search: discovering relevant scientific literature. In: Proceedings of SIGKDD, pp. 439\u2013447 (2011)","DOI":"10.1145\/2020408.2020479"},{"key":"840_CR13","doi-asserted-by":"crossref","unstructured":"El-Arini, K., Veda, G., Shahaf, D., Guestrin, C.: Turning down the noise in the blogosphere. In: Proceedings of SIGKDD, pp. 289\u2013298 (2009)","DOI":"10.21236\/ADA501771"},{"key":"840_CR14","unstructured":"Elenberg, E., Dimakis, A.G., Feldman, M., Karbasi, A.: Streaming weak submodularity: interpreting neural networks on the fly. In: Proceedings of NIPS, pp. 4044\u20134054 (2017)"},{"key":"840_CR15","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. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"840_CR16","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10898-004-5909-z","volume":"32","author":"B Goldengorin","year":"2005","unstructured":"Goldengorin, B., Ghosh, D.: A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem. J. Glob. Optim. 32, 65\u201382 (2005)","journal-title":"J. Glob. Optim."},{"key":"840_CR17","first-page":"427","volume":"42","author":"D Golovin","year":"2011","unstructured":"Golovin, D., Krause, A.: Adaptive submodularity: theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42, 427\u2013486 (2011)","journal-title":"J. Artif. Intell. Res."},{"key":"840_CR18","unstructured":"Gomes, R., Krause, A.: Budgeted nonparametric learning from data streams. In: Proceedings of ICML, pp. 391\u2013398 (2010)"},{"key":"840_CR19","first-page":"36","volume":"8","author":"M Gomez Rodriguez","year":"2018","unstructured":"Gomez Rodriguez, M., Leskovec, J., Krause, A.: Inferring networks of diffusion and influence. ACM Trans. Knowl. Discov. D 8, 36\u201339 (2018)","journal-title":"ACM Trans. Knowl. Discov. D"},{"key":"840_CR20","unstructured":"Guha, S., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams. In: Proceedings of FOCS, pp. 359\u2013366 (2000)"},{"key":"840_CR21","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s10898-013-0134-2","volume":"59","author":"K Kampa","year":"2014","unstructured":"Kampa, K., Mehta, S., Chou, C.A., Chaovalitwongse, W.A., Grabowski, T.J.: Sparse optimization in feature selection: application in neuroimaging. J. Glob. Optim. 59, 439\u2013457 (2014)","journal-title":"J. Glob. Optim."},{"key":"840_CR22","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of SIGKDD, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"key":"840_CR23","unstructured":"Khanna, R., Elenberg, E., Dimakis, A.G., Negahban, S., Ghosh, J.: Scalable greedy feature selection via weak submodularity. In: Proceedings of AISTATS, pp. 1560\u20131568 (2017)"},{"key":"840_CR24","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1017\/CBO9781139177801.004","volume-title":"Submodular function maximization. In tractability: practical approaches to hard problems","author":"A Krause","year":"2014","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. In tractability: practical approaches to hard problems, pp. 71\u2013104. Cambridge University Press, Cambridge (2014)"},{"key":"840_CR25","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, A., Guestrin, C.: Nearoptimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235\u2013284 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"840_CR26","unstructured":"Kuhnle, A., Smith, J.D., Crawford, V.G., Thai, M.T.: Fast maximization of non-submodular, monotonic functions on the integer lattice. In: Proceedings of ICML, pp. 2791\u20132800 (2018)"},{"key":"840_CR27","unstructured":"Lawrence, N., Seeger, M., Herbrich, R.: Fast sparse gaussian process methods: the informative vector machine. In: Proceedings of NIPS, pp. 625\u2013632 (2003)"},{"key":"840_CR28","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B Lehmann","year":"2006","unstructured":"Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55, 270\u2013296 (2006)","journal-title":"Games Econ. Behav."},{"key":"840_CR29","doi-asserted-by":"crossref","unstructured":"Lin, Y., Chen, W., Lui, J.C.S.: Boosting information spread: an algorithmic approach. In: Proceedings of ICDE, pp. 883\u2013894 (2017)","DOI":"10.1109\/ICDE.2017.137"},{"key":"840_CR30","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondr\u00e1k, J., Krause, A.: Lazier than lazy greedy. In: Proceedings of AAAI, pp. 1812\u20131818 (2015)","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"840_CR31","unstructured":"Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular maximization: identifying representative elements in massive data. In: Proceedings of NIPS, pp. 2049\u20132057 (2013)"},{"key":"840_CR32","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci. 1, 117\u2013236 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"840_CR33","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-I. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"840_CR34","unstructured":"Norouzi-Fard, A., Tarnawski, J., Mitrovic, S., Zandieh, A., Mousavifar, A., Svensson, O.: Beyond $$1\/2$$-approximation for submodular maximization on massive data streams. In: Proceedings of ICML, pp. 3826\u20133835 (2018)"},{"key":"840_CR35","doi-asserted-by":"publisher","first-page":"14367","DOI":"10.1109\/ACCESS.2018.2809547","volume":"6","author":"Q Yu","year":"2018","unstructured":"Yu, Q., Li, H., Liao, Y., Cui, S.: Fast budgeted influence maximization over multi-action event logs. IEEE Access 6, 14367\u201314378 (2018)","journal-title":"IEEE Access"},{"key":"840_CR36","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/s10898-009-9511-2","volume":"48","author":"X Zhu","year":"2010","unstructured":"Zhu, X., Yu, J., Lee, W., Kim, D., Shan, S., Du, D.Z.: New dominating sets in social networks. J. Glob. Optim. 48, 633\u2013642 (2010)","journal-title":"J. Glob. Optim."},{"key":"840_CR37","unstructured":"Zoubin, G.: Scaling the indian buffet process via submodular maximization. In: Proceedings of ICML, pp. 1013\u20131021 (2013)"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-019-00840-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-019-00840-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-019-00840-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T22:22:53Z","timestamp":1664662973000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-019-00840-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,16]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["840"],"URL":"https:\/\/doi.org\/10.1007\/s10898-019-00840-8","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,16]]},"assertion":[{"value":"25 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}