{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:42:13Z","timestamp":1767339733543,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2023,2,23]],"date-time":"2023-02-23T00:00:00Z","timestamp":1677110400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,2,23]],"date-time":"2023-02-23T00:00:00Z","timestamp":1677110400000},"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":["11991022"],"award-info":[{"award-number":["11991022"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["E1E40107X2","12071459"],"award-info":[{"award-number":["E1E40107X2","12071459"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1007\/s11590-023-01979-w","type":"journal-article","created":{"date-parts":[[2023,2,23]],"date-time":"2023-02-23T07:03:11Z","timestamp":1677135791000},"page":"1643-1667","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions"],"prefix":"10.1007","volume":"17","author":[{"given":"Cheng","family":"Lu","sequence":"first","affiliation":[]},{"given":"Wenguo","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Suixiang","family":"Gao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,23]]},"reference":[{"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)","key":"1979_CR1","DOI":"10.1145\/2623330.2623637"},{"unstructured":"Bai, W., Bilmes, J.: Greed is still good: maximizing monotone submodular+ supermodular (bp) functions. In: International Conference on Machine Learning, pp. 304\u2013313. PMLR (2018)","key":"1979_CR2"},{"unstructured":"Bai, W., Iyer, R., Wei, K., Bilmes, J.: Algorithms for optimizing the ratio of submodular functions. In: International Conference on Machine Learning, pp. 2751\u20132759. PMLR (2016)","key":"1979_CR3"},{"unstructured":"Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: International Conference on Machine Learning, pp. 498\u2013507. PMLR, (2017)","key":"1979_CR4"},{"unstructured":"Bogunovic, I., Zhao, J., Cevher, V.: Robust maximization of non-submodular objectives. In: International Conference on Artificial Intelligence and Statistics, pp. 890\u2013899. PMLR (2018)","key":"1979_CR5"},{"issue":"3","key":"1979_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3309764","volume":"15","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder, N., Feldman, Moran, Schwartz, R.: Online submodular maximization with preemption. ACM Trans. Algorithms (TALG) 15(3), 1\u201331 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"1979_CR7","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.dam.2015.01.026","volume":"186","author":"Kevin M Byrnes","year":"2015","unstructured":"Byrnes, Kevin M.: A tight analysis of the submodular-supermodular procedure. Discret. Appl. Math. 186, 275\u2013282 (2015)","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"1979_CR8","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, Chandra, Pal, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"unstructured":"Chen, L., Feldman, M., Karbasi, A.: Weakly submodular maximization beyond cardinality constraints: does randomization help greedy? In: International Conference on Machine Learning, pp. 804\u2013813. PMLR (2018)","key":"1979_CR9"},{"issue":"3","key":"1979_CR10","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\u00e9rard.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discret. Appl. Math. 7(3), 251\u2013274 (1984)","journal-title":"Discret. Appl. Math."},{"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 International Conference on Machine Learning, pp. 1057\u20131064 (2011)","key":"1979_CR11"},{"issue":"1","key":"1979_CR12","first-page":"74","volume":"19","author":"A Das","year":"2018","unstructured":"Das, A., Kempe, David: Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. J. Mach. Learn. Res. 19(1), 74\u2013107 (2018)","journal-title":"J. Mach. Learn. Res."},{"unstructured":"El\u00a0Halabi, M., Bach, F., Cevher, V.: Combinatorial penalties: which structures are preserved by convex relaxations? In: International Conference on Artificial Intelligence and Statistics, pp. 1551\u20131560. PMLR (2018)","key":"1979_CR13"},{"unstructured":"Elenberg, E.R., Dimakis, A.G., Feldman, M., Karbasi, A.: Streaming weak submodularity: interpreting neural networks on the fly. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 4047\u20134057 (2017)","key":"1979_CR14"},{"issue":"2","key":"1979_CR15","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/s00453-012-9646-2","volume":"66","author":"U Feige","year":"2013","unstructured":"Feige, U., Immorlica, N., Mirrokni, V.S., Nazerzadeh, H.: Pass approximation: a framework for analyzing and designing heuristics. Algorithmica 66(2), 450\u2013478 (2013)","journal-title":"Algorithmica"},{"issue":"3","key":"1979_CR16","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-020-00757-9","volume":"83","author":"Moran Feldman","year":"2021","unstructured":"Feldman, Moran: Guess free maximization of submodular and linear sums. Algorithmica 83(3), 853\u2013878 (2021)","journal-title":"Algorithmica"},{"unstructured":"Gatmiry, K., Gomez-Rodriguez, M.: Non-submodular function maximization subject to a matroid constraint, with applications. arXiv preprint arXiv:1811.07863, (2018)","key":"1979_CR17"},{"key":"1979_CR18","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.tcs.2020.05.018","volume":"853","author":"S Gong","year":"2021","unstructured":"Gong, S., Nong, Q., Sun, T., Fang, Q., Dingzhu, Du., Shao, Xiaoyu: Maximize a monotone function with a generic submodularity ratio. Theor. Comput. Sci. 853, 16\u201324 (2021)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: International Conference on Machine Learning, pp. 2634\u20132643. PMLR (2019)","key":"1979_CR19"},{"unstructured":"Iyer, R., Bilmes, J.: Algorithms for approximate minimization of the difference between submodular functions, with applications. In: Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pp. 407\u2013417 (2012)","key":"1979_CR20"},{"issue":"10","key":"1979_CR21","doi-asserted-by":"publisher","first-page":"1756","DOI":"10.14778\/3467861.3467866","volume":"14","author":"Y Tianyuan Jin","year":"2021","unstructured":"Tianyuan Jin, Y., Yang, Renchi Yang, Shi, J., Huang, K., Xiao, X.: Unconstrained submodular maximization with modular costs: tight approximation and application to profit maximization. Proc. VLDB Endow. 14(10), 1756\u20131768 (2021)","journal-title":"Proc. VLDB Endow."},{"unstructured":"Kazemi, E., Mitrovic, M., Zadimoghaddam, M., Lattanzi, S., Karbasi, A.: Submodular streaming in all its glory: tight approximation, minimum memory and low adaptive complexity. In: International Conference on Machine Learning, pp. 3311\u20133320. PMLR (2019)","key":"1979_CR22"},{"unstructured":"Kazemi, E., Minaee, S., Feldman, M., Karbasi, A.: Regularized submodular maximization at scale. In: International Conference on Machine Learning, pp. 5356\u20135366. PMLR (2021)","key":"1979_CR23"},{"doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137\u2013146 (2003)","key":"1979_CR24","DOI":"10.1145\/956750.956769"},{"unstructured":"Krause, A., Guestrin, C.: Near-optimal observation selection using submodular functions. In: AAAI. vol. 7, pp. 1650\u20131654 (2007)","key":"1979_CR25"},{"issue":"Feb","key":"1979_CR26","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, Ajit, Guestrin, C.: Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9(Feb), 235\u2013284 (2008)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"1979_CR27","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, Daniel, Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270\u2013296 (2006)","journal-title":"Games Econ. Behav."},{"key":"1979_CR28","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.tcs.2021.01.020","volume":"858","author":"Z Liu","year":"2021","unstructured":"Liu, Z., Chen, L., Chang, H., Donglei, D., Zhang, X.: Online algorithms for bp functions maximization. Theor. Comput. Sci. 858, 114\u2013121 (2021)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Narasimhan, M., Bilmes, J.A.: A submodular-supermodular procedure with applications to discriminative structure learning. arXiv preprint arXiv:1207.1404, (2012)","key":"1979_CR29"},{"issue":"1","key":"1979_CR30","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, Laurence A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-i. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"doi-asserted-by":"crossref","unstructured":"Nikolakaki, S.M., Ene, A., Terzi, E.: An efficient framework for balancing submodularity and cost. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1256\u20131266 (2021)","key":"1979_CR31","DOI":"10.1145\/3447548.3467367"},{"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: International Conference on Machine Learning, pp. 3829\u20133838. PMLR (2018)","key":"1979_CR32"},{"unstructured":"Perrault, P., Healey, J., Wen, Z., Valko, M.: On the approximation relationship between optimizing ratio of submodular (rs) and difference of submodular (ds) functions. arXiv preprint arXiv:2101.01631, (2021)","key":"1979_CR33"},{"issue":"4","key":"1979_CR34","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1287\/moor.2016.0842","volume":"42","author":"M Sviridenko","year":"2017","unstructured":"Sviridenko, M., Vondr\u00e1k, Jan, Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197\u20131218 (2017)","journal-title":"Math. Oper. Res."},{"key":"1979_CR35","first-page":"253","volume":"23","author":"J Vondr\u00e1k","year":"2010","unstructured":"Vondr\u00e1k, J.: Submodularity and curvature: the optimal algorithm (combinatorial optimization and discrete algorithms). RIMS Kokyuroku Bessatsu 23, 253\u2013266 (2010)","journal-title":"RIMS Kokyuroku Bessatsu"},{"issue":"4","key":"1979_CR36","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/s10898-019-00840-8","volume":"76","author":"Y Wang","year":"2020","unstructured":"Wang, Y., Dachuan, Xu., Wang, Y., Zhang, D.: Non-submodular maximization on massive data streams. J. Glob. Optim. 76(4), 729\u2013743 (2020)","journal-title":"J. Glob. Optim."},{"key":"1979_CR37","first-page":"27890","volume":"34","author":"F Yang","year":"2021","unstructured":"Yang, F., He, Kai, Yang, L., Hongxia, D., Yang, J., Yang, Bo., Sun, Liang: Learning interpretable decision rule sets: a submodular optimization approach. Adv. Neural Inf. Process. Syst. 34, 27890\u201327902 (2021)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"4","key":"1979_CR38","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1162\/08997660360581958","volume":"15","author":"AL Yuille","year":"2003","unstructured":"Yuille, A.L., Rangarajan, A.: The concave-convex procedure. Neural Comput. 15(4), 915\u2013936 (2003)","journal-title":"Neural Comput."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-01979-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-023-01979-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-01979-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T13:25:33Z","timestamp":1689168333000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-023-01979-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,23]]},"references-count":38,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1979"],"URL":"https:\/\/doi.org\/10.1007\/s11590-023-01979-w","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2023,2,23]]},"assertion":[{"value":"23 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}