{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:21:17Z","timestamp":1740122477905,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:00:00Z","timestamp":1708560000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:00:00Z","timestamp":1708560000000},"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","12071459"],"award-info":[{"award-number":["11991022","12071459"]}],"id":[{"id":"10.13039\/501100001809","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":[[2024,7]]},"DOI":"10.1007\/s10898-024-01371-7","type":"journal-article","created":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T02:02:41Z","timestamp":1708567361000},"page":"777-801","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast deterministic algorithms for non-submodular maximization with strong performance guarantees"],"prefix":"10.1007","volume":"89","author":[{"given":"Cheng","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8441-7334","authenticated-orcid":false,"given":"Wenguo","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,22]]},"reference":[{"issue":"1","key":"1371_CR1","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."},{"key":"1371_CR2","unstructured":"Goldengorin, B., Tijssen, G.A., Tso, M.: The maximization of submodular functions: old and new proofs for the correctness of the dichotomy algorithm. Unpublished manuscript, https:\/\/pure.rug.nl\/ws\/portalfiles\/portal\/3156943\/99a17.pdf (1999)"},{"issue":"1","key":"1371_CR3","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":"1371_CR4","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":"4","key":"1371_CR5","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(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"1371_CR6","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\u2013Edmonds theorem. Discrete Appl. Math. 7(3), 251\u2013274 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"1371_CR7","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s11590-016-1039-z","volume":"11","author":"J Laitila","year":"2017","unstructured":"Laitila, J., Moilanen, A.: New performance guarantees for the greedy maximization of submodular set functions. Optim. Lett. 11(4), 655\u2013665 (2017)","journal-title":"Optim. Lett."},{"issue":"4","key":"1371_CR8","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."},{"issue":"3","key":"1371_CR9","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-020-00757-9","volume":"83","author":"M Feldman","year":"2021","unstructured":"Feldman, M.: Guess free maximization of submodular and linear sums. Algorithmica 83(3), 853\u2013878 (2021)","journal-title":"Algorithmica"},{"key":"1371_CR10","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondr\u00e1k, J., Krause, A.: Lazier than lazy greedy. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI), vol. 29, pp. 1812\u20131818 (2015). AAAI","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"1371_CR11","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1497\u20131514 (2014). SIAM","DOI":"10.1137\/1.9781611973402.110"},{"issue":"2","key":"1371_CR12","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/moor.2016.0809","volume":"42","author":"N Buchbinder","year":"2017","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Comparing apples and oranges: query trade-off in submodular maximization. Math. Oper. Res. 42(2), 308\u2013329 (2017)","journal-title":"Math. Oper. Res."},{"key":"1371_CR13","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: Dedicated to the Memory of D.R. Fulkerson. Mathematical Programming Studies, vol. 8, pp. 73\u201387. Springer, Berlin (1978)","DOI":"10.1007\/BFb0121195"},{"issue":"6","key":"1371_CR14","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, 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":"2","key":"1371_CR15","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":"1371_CR16","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 (ICML), pp. 1057\u20131064 (2011)"},{"key":"1371_CR17","unstructured":"El\u00a0Halabi, M., Bach, F., Cevher, V.: Combinatorial penalties: Which structures are preserved by convex relaxations? In: Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 84, pp. 1551\u20131560 (2018)"},{"key":"1371_CR18","unstructured":"Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of the 34th International Conference on Machine Learning (ICML), vol. 70, pp. 498\u2013507 (2017)"},{"key":"1371_CR19","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., Du, D., Shao, X.: Maximize a monotone function with a generic submodularity ratio. Theoret. Comput. Sci. 853, 16\u201324 (2021)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1371_CR20","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/s10957-022-02145-5","volume":"196","author":"M-J Shi","year":"2023","unstructured":"Shi, M.-J., Yang, Z., Wang, W.: Greedy guarantees for non-submodular function maximization under independent system constraint with applications. J. Optim. Theory Appl. 196(2), 516\u2013543 (2023)","journal-title":"J. Optim. Theory Appl."},{"key":"1371_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-022-00444-2","author":"M-J Shi","year":"2022","unstructured":"Shi, M.-J., Wang, W.: Greedy is good: constrained non-submodular function maximization via weak submodularity. J. Oper. Res. Soc. China (2022). https:\/\/doi.org\/10.1007\/s40305-022-00444-2","journal-title":"J. Oper. Res. Soc. China"},{"key":"1371_CR22","unstructured":"Bai, W., Bilmes, J.A.: Greed is still good: Maximizing monotone suBmodular + suPermodular (BP) functions. In: Proceedings of the 35th International Conference on Machine Learning (ICML), vol. 80, pp. 304\u2013313 (2018)"},{"issue":"4","key":"1371_CR23","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/s10898-021-01123-x","volume":"83","author":"C Lu","year":"2022","unstructured":"Lu, C., Yang, W., Yang, R., Gao, S.: Maximizing a non-decreasing non-submodular function subject to various types of constraints. J. Global Optim. 83(4), 727\u2013751 (2022)","journal-title":"J. Global Optim."},{"issue":"1","key":"1371_CR24","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10898-021-01063-6","volume":"82","author":"Z Liu","year":"2022","unstructured":"Liu, Z., Guo, L., Du, D., Xu, D., Zhang, X.: Maximization problems of balancing submodular relevance and supermodular diversity. J. Global Optim. 82(1), 179\u2013194 (2022)","journal-title":"J. Global Optim."},{"key":"1371_CR25","unstructured":"Narang, A., Sadeghi, O., Ratliff, L.J., Fazel, M., Bilmes, J.: Interactive combinatorial bandits: Balancing competitivity and complementarity. arXiv:2207.03091 (2022)"},{"issue":"1","key":"1371_CR26","doi-asserted-by":"publisher","first-page":"46","DOI":"10.26599\/TST.2022.9010013","volume":"29","author":"Z Zhang","year":"2023","unstructured":"Zhang, Z., Meng, K., Du, D., Zhou, Y.: Maximizing submodular + supermodular functions subject to a fairness constraint. Tsinghua Sci. Technol. 29(1), 46\u201355 (2023)","journal-title":"Tsinghua Sci. Technol."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01371-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01371-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01371-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T04:14:37Z","timestamp":1718424877000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01371-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,22]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1371"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01371-7","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2024,2,22]]},"assertion":[{"value":"18 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2024","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 no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}