{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:12:38Z","timestamp":1757542358436,"version":"3.41.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T00:00:00Z","timestamp":1742256000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T00:00:00Z","timestamp":1742256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s10898-025-01473-w","type":"journal-article","created":{"date-parts":[[2025,3,18]],"date-time":"2025-03-18T03:35:11Z","timestamp":1742268911000},"page":"453-481","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Revisiting non-monotone regularized submodular maximization: bi-criteria and PASS approximations"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1076-0869","authenticated-orcid":false,"given":"Cheng","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,18]]},"reference":[{"issue":"8","key":"1473_CR1","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G Cornu\u00e9jols","year":"1977","unstructured":"Cornu\u00e9jols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manage. Sci. 23(8), 789\u2013810 (1977)","journal-title":"Manage. Sci."},{"key":"1473_CR2","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0167-5060(08)70732-5","volume":"1","author":"G Cornu\u00e9jols","year":"1977","unstructured":"Cornu\u00e9jols, G., Fisher, M., Nemhauser, G.L.: On the uncapacitated location problem. studies in integer programming. Annal. Discrete Math. 1, 163\u2013177 (1977)","journal-title":"Annal. Discrete Math."},{"issue":"2","key":"1473_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), 149\u2013156 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1473_CR4","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1145\/972639.972644","volume":"51","author":"J Kleinberg","year":"2004","unstructured":"Kleinberg, J., Papadimitriou, C., Raghavan, P.: Segmentation problems. J. ACM (JACM) 51(2), 263\u2013280 (2004)","journal-title":"J. ACM (JACM)"},{"key":"1473_CR5","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 International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1256\u20131266. ACM (2021)","DOI":"10.1145\/3447548.3467367"},{"issue":"10","key":"1473_CR6","doi-asserted-by":"publisher","first-page":"1756","DOI":"10.14778\/3467861.3467866","volume":"14","author":"T Jin","year":"2021","unstructured":"Jin, T., Yang, Y., Yang, R., Shi, J., Huang, K., Xiao, X.: Unconstrained submodular maximization with modular costs: tight approximation and application to profit maximization. Proc. VLDB Endowment 14(10), 1756\u20131768 (2021)","journal-title":"Proc. VLDB Endowment"},{"key":"1473_CR7","unstructured":"Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In: Proceedings of the 36th International Conference on Machine Learning (ICML), vol. 97, pp. 2634\u20132643 (2019). PMLR"},{"key":"1473_CR8","unstructured":"Kazemi, E., Minaee, S., Feldman, M., Karbasi, A.: Regularized submodular maximization at scale. In: Proceedings of the 38th International Conference on Machine Learning (ICML), vol. 139, pp. 5356\u20135366 (2021). PMLR"},{"issue":"2","key":"1473_CR9","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"},{"key":"1473_CR10","doi-asserted-by":"crossref","unstructured":"Lu, C.: Regularized monotone submodular maximization: Bi-criteria and PASS approximations. Submitted to Discrete Optimization (2024)","DOI":"10.1007\/s10898-025-01473-w"},{"issue":"3","key":"1473_CR11","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":"1473_CR12","unstructured":"Bodek, K., Feldman, M.: Maximizing sums of non-monotone submodular and linear functions: Understanding the unconstrained case. In: 30th Annual European Symposium on Algorithms (ESA), vol. 244, pp. 23\u201312317 (2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"4","key":"1473_CR13","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":"7","key":"1473_CR14","doi-asserted-by":"publisher","first-page":"1643","DOI":"10.1007\/s11590-023-01979-w","volume":"17","author":"C Lu","year":"2023","unstructured":"Lu, C., Yang, W., Gao, S.: Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions. Optim. Lett. 17(7), 1643\u20131667 (2023)","journal-title":"Optim. Lett."},{"key":"1473_CR15","doi-asserted-by":"crossref","unstructured":"Nikolakaki, S.M., Ene, A., Terzi, E.: An efficient framework for balancing submodularity and cost. arXiv:2002.07782 (2020)","DOI":"10.1145\/3447548.3467367"},{"key":"1473_CR16","doi-asserted-by":"publisher","unstructured":"Lu, C., Yang, W., Gao, S.: Regularized nonmonotone submodular maximization. Optimization (2023) https:\/\/doi.org\/10.1080\/02331934.2023.2173968","DOI":"10.1080\/02331934.2023.2173968"},{"key":"1473_CR17","doi-asserted-by":"publisher","unstructured":"Qi, B.: On maximizing sums of non-monotone submodular and linear functions. Algorithmica, 1\u201355 (2023) https:\/\/doi.org\/10.1007\/s00453-023-01183-3","DOI":"10.1007\/s00453-023-01183-3"},{"issue":"1","key":"1473_CR18","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."},{"key":"1473_CR19","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1433\u20131452 (2014). SIAM","DOI":"10.1137\/1.9781611973730.80"},{"issue":"2","key":"1473_CR20","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":"1473_CR21","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Vondr\u00e1k, J.: Submodular maximization by simulated annealing. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1098\u20131116 (2011). SIAM","DOI":"10.1137\/1.9781611973082.83"},{"key":"1473_CR22","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J.S., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 570\u2013579 (2011). IEEE Computer Society","DOI":"10.1109\/FOCS.2011.46"},{"key":"1473_CR23","doi-asserted-by":"crossref","unstructured":"Ene, A., Nguyen, H.L.: Constrained submodular maximization: Beyond 1\/e. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 248\u2013257 (2016). IEEE Computer Society","DOI":"10.1109\/FOCS.2016.34"},{"issue":"3","key":"1473_CR24","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1287\/moor.2018.0955","volume":"44","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder, N., Feldman, M.: Constrained submodular maximization via a nonsymmetric technique. Math. Oper. Res. 44(3), 988\u20131005 (2019)","journal-title":"Math. Oper. Res."},{"key":"1473_CR25","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Constrained submodular maximization via new bounds for DR-submodular functions. arXiv:2311.01129 (2023)","DOI":"10.1145\/3618260.3649630"},{"issue":"4","key":"1473_CR26","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1473_CR27","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/130929205","volume":"44","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.: A tight linear time ($$1\/2$$)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384\u20131402 (2015)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1473_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3184990","volume":"14","author":"N Buchbinder","year":"2018","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. ACM Transactions on Algorithms (TALG) 14(3), 1\u201320 (2018)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"2","key":"1473_CR29","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."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01473-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-025-01473-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01473-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T06:28:50Z","timestamp":1748845730000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-025-01473-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,18]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["1473"],"URL":"https:\/\/doi.org\/10.1007\/s10898-025-01473-w","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2025,3,18]]},"assertion":[{"value":"10 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2025","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 author declares no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}