{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T18:54:49Z","timestamp":1771959289420,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,2,16]],"date-time":"2021-02-16T00:00:00Z","timestamp":1613433600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,16]],"date-time":"2021-02-16T00:00:00Z","timestamp":1613433600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ARC Discovery Early Career Researcher Award","award":["DE160100850"],"award-info":[{"award-number":["DE160100850"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s11047-021-09841-7","type":"journal-article","created":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T10:05:34Z","timestamp":1613729134000},"page":"561-575","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations"],"prefix":"10.1007","volume":"20","author":[{"given":"Francesco","family":"Quinzan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"G\u00f6bel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,16]]},"reference":[{"key":"9841_CR1","doi-asserted-by":"crossref","unstructured":"Ageev AA, Sviridenko M (1999) An 0.828-approximation algorithm for the uncapacitated facility location problem an 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Appl Math 93(2\u20133):149\u2013156","DOI":"10.1016\/S0166-218X(99)00103-1"},{"issue":"4","key":"9841_CR2","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0167-7152(84)90020-8","volume":"2","author":"WF Caselton","year":"1984","unstructured":"Caselton WF, Zidek J (1984) Optimal monitoring network designs optimal monitoring network designs. Stat Probab Lett 2(4):223\u2013227","journal-title":"Stat Probab Lett"},{"key":"9841_CR3","volume-title":"Evolutionary algorithms in engineering applications","author":"D Dasgupta","year":"2013","unstructured":"Dasgupta D, Michalewicz Z (2013) Evolutionary algorithms in engineering applications. Springer, Berlin"},{"issue":"1","key":"9841_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/EVCO_a_00055","volume":"21","author":"B Doerr","year":"2013","unstructured":"Doerr B, Jansen T, Sudholt D, Winzen C, Zarges C (2013) Mutation rate matters even when optimizing monotonic functions mutation rate matters even when optimizing monotonic functions. Evol Comput 21(1):1\u201327","journal-title":"Evol Comput"},{"issue":"4","key":"9841_CR5","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr B, Johannsen D, Winzen C (2012) Multiplicative drift analysis. Algorithmica 64(4):673\u2013697","journal-title":"Algorithmica"},{"key":"9841_CR6","doi-asserted-by":"crossref","unstructured":"Doerr B, Le HP, Makhmara R, Nguyen TD (2017) Fast genetic algorithms. In: Proceedings of GECCO, pp 777\u2013784","DOI":"10.1145\/3071178.3071301"},{"key":"9841_CR7","doi-asserted-by":"crossref","unstructured":"Doerr C, Wagner M (2018a) Sensitivity of parameter control mechanisms with respect to their initialization. In: Proceedings of of PPSN, pp 360\u2013372","DOI":"10.1007\/978-3-319-99259-4_29"},{"key":"9841_CR8","doi-asserted-by":"crossref","unstructured":"Doerr C, Wagner M (2018b) Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In: Proceedings of GECCO, pp 943\u2013950","DOI":"10.1145\/3205455.3205560"},{"issue":"1\u20132","key":"9841_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S Droste","year":"2002","unstructured":"Droste S, Jansen T, Wegener I (2002) On the analysis of the (1+1) evolutionary algorithm. Theor Comput Sci 276(1\u20132):51\u201381","journal-title":"Theor Comput Sci"},{"issue":"2","key":"9841_CR10","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/4235.771166","volume":"3","author":"AE Eiben","year":"1999","unstructured":"Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124\u2013141","journal-title":"IEEE Trans Evol Comput"},{"key":"9841_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05094-1","volume-title":"Introduction to evolutionary computation","author":"AE Eiben","year":"2003","unstructured":"Eiben AE, Smith JE (2003) Introduction to evolutionary computation. Springer, Berlin"},{"issue":"4","key":"9841_CR12","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige U, Mirrokni VS, Vondr\u00e1k J (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133\u20131153","journal-title":"SIAM J Comput"},{"key":"9841_CR13","doi-asserted-by":"crossref","unstructured":"Friedrich T, G\u00f6bel A, Quinzan F, Wagner M (2018a) Heavy-tailed mutation operators in single-objective combinatorial optimization. In: Proceedings of PPSN, pp 134\u2013145","DOI":"10.1007\/978-3-319-99253-2_11"},{"issue":"4","key":"9841_CR14","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1162\/EVCO_a_00003","volume":"18","author":"T Friedrich","year":"2010","unstructured":"Friedrich T, He J, Hebbinghaus N, Neumann F, Witt C (2010) Approximating covering problems by randomized search heuristics using multi-objective models. Evol Comput 18(4):617\u2013633","journal-title":"Evol Comput"},{"issue":"4","key":"9841_CR15","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1162\/EVCO_a_00159","volume":"23","author":"T Friedrich","year":"2015","unstructured":"Friedrich T, Neumann F (2015) Maximizing submodular functions under matroid constraints by evolutionary algorithms. Evol Comput 23(4):543\u2013558","journal-title":"Evol Comput"},{"key":"9841_CR16","doi-asserted-by":"crossref","unstructured":"Friedrich T, Quinzan F, Wagner M (2018b) Escaping large deceptive basins of attraction with heavy-tailed mutation operators. In Proceedings of GECCO, pp 293\u2013300","DOI":"10.1145\/3205455.3205515"},{"issue":"6","key":"9841_CR17","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115\u20131145","journal-title":"J ACM"},{"issue":"4","key":"9841_CR18","first-page":"798","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad J (2001) Some optimal inapproximability results. J ACM 48(4):798\u2013859","journal-title":"Some optimal inapproximability results. J ACM"},{"issue":"1","key":"9841_CR19","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.jda.2005.01.002","volume":"4","author":"T Jansen","year":"2006","unstructured":"Jansen T, Wegener I (2006) On the analysis of a dynamic evolutionary algorithm. J Discrete Algorithms 4(1):181\u2013199","journal-title":"J Discrete Algorithms"},{"key":"9841_CR20","first-page":"85","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. Complexity of computer computations. Springer, US, Boston, pp 85\u2013103"},{"key":"9841_CR21","unstructured":"Krause A, Guestrin C (2007) Near-optimal observation selection using submodular functions. In Proceedings of AAAI, pp 1650\u20131654"},{"key":"9841_CR22","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause A, Singh AP, Guestrin C (2008) Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J Mach Learn Res 9:235\u2013284","journal-title":"J Mach Learn Res"},{"key":"9841_CR23","doi-asserted-by":"crossref","unstructured":"Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2009) Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of STOC, pp 323\u2013332","DOI":"10.1145\/1536414.1536459"},{"issue":"2","key":"9841_CR24","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 DJ, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econ Behav 55(2):270\u2013296","journal-title":"Games Econ Behav"},{"key":"9841_CR25","volume-title":"Probability and computing: randomization and probabilistic techniques in algorithms and data analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher M, Upfal E (2017) Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, Cambridge"},{"key":"9841_CR26","unstructured":"M\u00fchlenbein H (1992) How genetic algorithms really work: mutation and hillclimbing. In: Proceedings of PPSN, pp 15\u201326"},{"issue":"3","key":"9841_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math Oper Res 3(3):177\u2013188","journal-title":"Math Oper Res"},{"issue":"5","key":"9841_CR28","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1109\/TEVC.2009.2014362","volume":"13","author":"PS Oliveto","year":"2009","unstructured":"Oliveto PS, He J, Yao X (2009) Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Trans Evol Comput 13(5):1006\u20131029","journal-title":"IEEE Trans Evol Comput"},{"issue":"4","key":"9841_CR29","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1109\/TEVC.2017.2749263","volume":"22","author":"C Qian","year":"2018","unstructured":"Qian C, Shi J, Tang K, Zhou Z (2018) Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Trans Evol Comput 22(4):595\u2013608","journal-title":"IEEE Trans Evol Comput"},{"key":"9841_CR30","unstructured":"Qian C, Yu Y, Tang K, Yao X, Zhou Z (2017) Maximizing non-monotone\/non-submodular functions by multi-objective evolutionary algorithms. CoRRabs\/1711.07214"},{"issue":"8","key":"9841_CR31","doi-asserted-by":"publisher","first-page":"e0135749","DOI":"10.1371\/journal.pone.0135749","volume":"10","author":"RA Rhode","year":"2015","unstructured":"Rhode RA, Muller RA (2015) Air pollution in China: mapping of concentrations and sources. PLoS One 10(8):e0135749","journal-title":"PLoS One"},{"key":"9841_CR32","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization (Website). http:\/\/networkrepository.com","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"9841_CR33","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1613\/jair.2674","volume":"34","author":"A Singh","year":"2009","unstructured":"Singh A, Krause A, Guestrin C, Kaiser WJ (2009) Efficient informative sensing using multiple robots. J Artif Intell Res 34:707\u2013755","journal-title":"J Artif Intell Res"},{"key":"9841_CR34","doi-asserted-by":"crossref","unstructured":"Wagner M, Friedrich T, Lindauer M (2017) Improving local search in a minimum vertex cover solver for classes of networks. In: Proceedings of CEC, pp 1704\u20131711","DOI":"10.1109\/CEC.2017.7969507"},{"key":"9841_CR35","doi-asserted-by":"crossref","unstructured":"Wegener I (2001) Theoretical aspects of evolutionary algorithms. In: Proceedings of ICALP, pp 64\u201378","DOI":"10.1007\/3-540-48224-5_6"},{"key":"9841_CR36","unstructured":"Welsh DJ (2010) Matroid theory. Courier Corporation"},{"key":"9841_CR37","doi-asserted-by":"crossref","unstructured":"Witt C (2005) Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of STACS, pp 44\u201356","DOI":"10.1007\/978-3-540-31856-9_4"},{"issue":"1","key":"9841_CR38","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1198\/108571106X99751","volume":"11","author":"Z Zhu","year":"2006","unstructured":"Zhu Z, Stein ML (2006) Spatial sampling design for prediction with estimated parameters. J Agric Biol Environ Stat 11(1):24\u201344","journal-title":"J Agric Biol Environ Stat"},{"issue":"6","key":"9841_CR39","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1002\/env.769","volume":"17","author":"DL Zimmerman","year":"2006","unstructured":"Zimmerman DL (2006) Optimal network design for spatial prediction, covariance parameter estimation, and empirical prediction. Environmetrics 17(6):635\u2013652","journal-title":"Environmetrics"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09841-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-021-09841-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09841-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,18]],"date-time":"2022-12-18T05:15:57Z","timestamp":1671340557000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-021-09841-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,16]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["9841"],"URL":"https:\/\/doi.org\/10.1007\/s11047-021-09841-7","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,16]]},"assertion":[{"value":"8 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}