{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:14:59Z","timestamp":1762272899666,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T00:00:00Z","timestamp":1642550400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T00:00:00Z","timestamp":1642550400000},"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":"publisher","award":["11991022","12071459"],"award-info":[{"award-number":["11991022","12071459"]}],"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":["E1E40107"],"award-info":[{"award-number":["E1E40107"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s10898-021-01123-x","type":"journal-article","created":{"date-parts":[[2022,1,19]],"date-time":"2022-01-19T07:04:35Z","timestamp":1642575875000},"page":"727-751","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Maximizing a non-decreasing non-submodular function subject to various types of constraints"],"prefix":"10.1007","volume":"83","author":[{"given":"Cheng","family":"Lu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8441-7334","authenticated-orcid":false,"given":"Wenguo","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Ruiqi","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Suixiang","family":"Gao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,19]]},"reference":[{"issue":"2","key":"1123_CR1","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1137\/S089548010036813X","volume":"14","author":"A Ageev","year":"2001","unstructured":"Ageev, A., Hassin, R., Sviridenko, M.: A 0.5-approximation algorithm for max dicut with given sizes of parts. SIAM J. Discret. Math. 14(2), 246\u2013255 (2001)","journal-title":"SIAM J. Discret. Math."},{"key":"1123_CR2","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)"},{"issue":"2","key":"1123_CR3","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1017\/S000497270004140X","volume":"1","author":"RA Brualdi","year":"1969","unstructured":"Brualdi, R.A.: Comments on bases in dependence structures. Bull. Aust. Math. Soc. 1(2), 161\u2013167 (1969)","journal-title":"Bull. Aust. Math. Soc."},{"issue":"6","key":"1123_CR4","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.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1123_CR5","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014)","journal-title":"SIAM J. Comput."},{"key":"1123_CR6","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)"},{"issue":"3","key":"1123_CR7","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.: 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."},{"key":"1123_CR8","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)"},{"issue":"1","key":"1123_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10115-014-0801-8","volume":"45","author":"AK Farahat","year":"2015","unstructured":"Farahat, A.K., Elgohary, A., Ghodsi, A., Kamel, M.S.: Greedy column subset selection for large-scale data sets. Knowl. Inf. Syst. 45(1), 1\u201334 (2015)","journal-title":"Knowl. Inf. Syst."},{"issue":"4","key":"1123_CR10","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 (JACM) 45(4), 634\u2013652 (1998)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"1123_CR11","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/130920277","volume":"43","author":"Y Filmus","year":"2014","unstructured":"Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2), 514\u2013542 (2014)","journal-title":"SIAM J. Comput."},{"key":"1123_CR12","doi-asserted-by":"crossref","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions\u2014ii. In: Polyhedral Combinatorics, pp. 73\u201387. Springer (1978)","DOI":"10.1007\/BFb0121195"},{"issue":"1","key":"1123_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for maxk-cut and max bisection. Algorithmica 18(1), 67\u201381 (1997)","journal-title":"Algorithmica"},{"key":"1123_CR14","unstructured":"Gatmiry, K., Gomez-Rodriguez, M.: Non-submodular function maximization subject to a matroid constraint, with applications. arXiv preprint arXiv:1811.07863 (2018)"},{"issue":"1","key":"1123_CR15","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.ejor.2008.08.022","volume":"198","author":"B Goldengorin","year":"2009","unstructured":"Goldengorin, B.: Maximization of submodular functions: theory and enumeration algorithms. Eur. J. Oper. Res. 198(1), 102\u2013112 (2009)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1123_CR16","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/s10898-019-00800-2","volume":"75","author":"S Gong","year":"2019","unstructured":"Gong, S., Nong, Q., Liu, W., Fang, Q.: Parametric monotone function maximization with matroid constraints. J. Global Optim. 75(3), 833\u2013849 (2019)","journal-title":"J. Global Optim."},{"key":"1123_CR17","doi-asserted-by":"crossref","unstructured":"Gong, S., Nong, Q., Sun, T., Fang, Q., Du, D., Shao, X.: Maximize a monotone function with a generic submodularity ratio. Theor. Comput. Sci. (2020)","DOI":"10.1016\/j.tcs.2020.05.018"},{"issue":"2","key":"1123_CR18","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"},{"key":"1123_CR19","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)"},{"issue":"4","key":"1123_CR20","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 (JACM) 48(4), 761\u2013777 (2001)","journal-title":"J. ACM (JACM)"},{"key":"1123_CR21","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)","DOI":"10.1145\/956750.956769"},{"issue":"1","key":"1123_CR22","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.S.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"1123_CR23","doi-asserted-by":"crossref","unstructured":"Krause, A., Golovin, D.: Submodular Function Maximization (2014)","DOI":"10.1017\/CBO9781139177801.004"},{"key":"1123_CR24","unstructured":"Krause, A., Guestrin, C.: Near-optimal observation selection using submodular functions. In: AAAI, Vol.\u00a07, pp. 1650\u20131654 (2007)"},{"key":"1123_CR25","unstructured":"Krause, A., Guestrin, C.E: Near-optimal nonmyopic value of information in graphical models. arXiv preprint arXiv:1207.1394 (2012)"},{"issue":"Feb","key":"1123_CR26","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, A., 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":"4","key":"1123_CR27","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795\u2013806 (2010)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1123_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 Econom. Behav. 55(2), 270\u2013296 (2006)","journal-title":"Games Econom. Behav."},{"key":"1123_CR29","unstructured":"Lin, H., Bilmes, J.: 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 (2010)"},{"issue":"3","key":"1123_CR30","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177\u2013188 (1978)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1123_CR31","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":"2","key":"1123_CR32","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theor. Ser. B 80(2), 346\u2013355 (2000)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"1","key":"1123_CR33","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."},{"issue":"4","key":"1123_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, J., 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":"1123_CR35","unstructured":"Thiery, T., Ward, J.: Two-sided weak submodularity for matroid constrained optimization and regression. arXiv preprint arXiv:2102.09644 (2021)"},{"key":"1123_CR36","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":"3","key":"1123_CR37","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1137\/16M1107644","volume":"33","author":"Y Yoshida","year":"2019","unstructured":"Yoshida, Y.: Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint. SIAM J. Discret. Math. 33(3), 1452\u20131471 (2019)","journal-title":"SIAM J. Discret. Math."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01123-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01123-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01123-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,17]],"date-time":"2022-07-17T07:04:54Z","timestamp":1658041494000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01123-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,19]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["1123"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01123-x","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2022,1,19]]},"assertion":[{"value":"24 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}