{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:39Z","timestamp":1740109299188,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T00:00:00Z","timestamp":1604448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s00453-020-00776-6","type":"journal-article","created":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T05:02:41Z","timestamp":1604466161000},"page":"3180-3208","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family Graphs"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1295-6715","authenticated-orcid":false,"given":"Andrew M.","family":"Sutton","sequence":"first","affiliation":[]},{"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,4]]},"reference":[{"key":"776_CR1","doi-asserted-by":"crossref","unstructured":"Antipov, D., Doerr, B., Fang, J., Hetet, T.: Runtime analysis for the ($$\\mu $$+$$\\lambda $$)\u00a0EA optimizing OneMax. In: Proc. of GECCO\u00a0\u201918, pp. 1459\u20131466. ACM Press (2018)","DOI":"10.1145\/3205455.3205627"},{"key":"776_CR2","doi-asserted-by":"crossref","first-page":"6566","DOI":"10.1016\/j.amc.2011.12.037","volume":"218","author":"MK Bakula","year":"2012","unstructured":"Bakula, M.K., Pe\u010dari\u0107, J., Peri\u0107, J.: On the converse Jensen inequality. Appl. Math. Comput. 218, 6566\u20136575 (2012)","journal-title":"Appl. Math. Comput."},{"key":"776_CR3","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1109\/TEVC.2017.2724201","volume":"22","author":"D Dang","year":"2018","unstructured":"Dang, D., Friedrich, T., K\u00f6tzing, T., Krejca, M.S., Lehre, P.K., Oliveto, P.S., Sudholt, D., Sutton, A.M.: Escaping local optima using crossover with emergent diversity. IEEE Trans. Evol. Comput. 22, 484\u2013497 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"776_CR4","first-page":"1","volume-title":"Probabilistic Tools for the Analysis of Randomized Optimization Heuristics","author":"B Doerr","year":"2020","unstructured":"Doerr, B.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Probabilistic Tools for the Analysis of Randomized Optimization Heuristics, pp. 1\u201387. Springer, Berlin (2020)"},{"key":"776_CR5","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","volume":"65","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65, 224\u2013250 (2013)","journal-title":"Algorithmica"},{"key":"776_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.tcs.2010.10.035","volume":"425","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Happ, E., Klein, C.: Crossover can provably be useful in evolutionary computation. Theorer. Comput. Sci. 425, 17\u201333 (2012)","journal-title":"Theorer. Comput. Sci."},{"key":"776_CR7","doi-asserted-by":"crossref","unstructured":"Doerr, B., Johannsen, D., K\u00f6tzing, T.: More effective crossover operators for the all-pairs shortest path problem. In: Proc. of PPSN\u00a0\u201910, pp. 184\u2013193. Springer (2010)","DOI":"10.1007\/978-3-642-15844-5_19"},{"key":"776_CR8","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.: Multiplicative drift analysis. Algorithmica 64, 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"776_CR9","doi-asserted-by":"crossref","unstructured":"Doerr, B., Theile, M.: Improved analysis methods for crossover-based algorithms. In: Proc. of GECCO\u00a0\u201909, pp. 247\u2013254. ACM Press (2009)","DOI":"10.1145\/1569901.1569937"},{"key":"776_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1214\/aoms\/1177731313","volume":"15","author":"H Geiringer","year":"1944","unstructured":"Geiringer, H.: On the probability theory of linkage in Mendelian heredity. Ann. Math. Stat. 15, 25\u201357 (1944)","journal-title":"Ann. Math. Stat."},{"key":"776_CR11","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J., Witt, C.: Rigorous runtime analysis of a ($$\\mu $$+1) ES for the Sphere function. In: Proc. of GECCO\u00a0\u201905, pp. 849\u2013856. ACM Press (2005)","DOI":"10.1145\/1068009.1068153"},{"key":"776_CR12","doi-asserted-by":"crossref","unstructured":"Jansen, T., Wegener, I.: On the analysis of evolutionary algorithms \u2013 a proof that crossover really can help. In: Proc. of 7th Annual European Symposium on Algorithms (ESA\u00a0\u201999), LNCS, vol. 1643, p. 700 (1999)","DOI":"10.1007\/3-540-48481-7_17"},{"key":"776_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.dam.2004.02.019","volume":"149","author":"T Jansen","year":"2005","unstructured":"Jansen, T., Wegener, I.: Real royal road functions\u2014where crossover provably is essential. Discret. Appl. Math. 149, 111\u2013125 (2005)","journal-title":"Discret. Appl. Math."},{"key":"776_CR14","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.tcs.2010.03.032","volume":"412","author":"T Jansen","year":"2011","unstructured":"Jansen, T., Zarges, C.: On benefits and drawbacks of aging strategies for randomized search heuristics. Theor. Comput. Sci. 412, 543\u2013559 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"776_CR15","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing, T., Sudholt, D., Theile, M.: How crossover helps in pseudo-boolean optimization. In: Proc. of GECCO\u00a0\u201911, pp. 989\u2013996. ACM Press (2011)","DOI":"10.1145\/2001576.2001711"},{"key":"776_CR16","doi-asserted-by":"crossref","unstructured":"Lehre, P.K.: Negative drift in populations. In: Proc. of PPSN\u00a0\u201910, pp. 244\u2013253. Springer (2010)","DOI":"10.1007\/978-3-642-15844-5_25"},{"key":"776_CR17","doi-asserted-by":"publisher","first-page":"1675","DOI":"10.1007\/s00500-010-0610-2","volume":"15","author":"PK Lehre","year":"2011","unstructured":"Lehre, P.K., Yao, X.: Crossover can be constructive when computing unique input\u2013output sequences. Soft Comput. 15, 1675\u20131687 (2011)","journal-title":"Soft Comput."},{"key":"776_CR18","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1109\/TEVC.2011.2112665","volume":"16","author":"PK Lehre","year":"2012","unstructured":"Lehre, P.K., Yao, X.: On the impact of mutation-selection balance on the runtime of evolutionary algorithms. IEEE Trans. Evol. Comput. 16, 225\u2013241 (2012)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"776_CR19","doi-asserted-by":"crossref","unstructured":"Lengler, J.: A general dichotomy of evolutionary algorithms on monotone functions. In: Proc. of PPSN\u00a0\u201918, pp. 3\u201315. Springer (2018). Extended version: arxiv.org\/abs\/1803.09227","DOI":"10.1007\/978-3-319-99259-4_1"},{"issue":"2","key":"776_CR20","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1093\/genetics\/134.2.627","volume":"134","author":"T Nagylaki","year":"1993","unstructured":"Nagylaki, T.: The evolution of multilocus systems under weak selection. Genetics 134(2), 627\u2013647 (1993)","journal-title":"Genetics"},{"key":"776_CR21","doi-asserted-by":"crossref","unstructured":"Neumann, F., Oliveto, P.S., Rudolph, G., Sudholt, D.: On the effectiveness of crossover for migration in parallel evolutionary algorithms. In: Proc. of GECCO\u00a0\u201911, pp. 1587\u20131594. ACM Press (2011)","DOI":"10.1145\/2001576.2001790"},{"key":"776_CR22","doi-asserted-by":"crossref","unstructured":"Oliveto, P.S., He, J., Yao, X.: Analysis of population-based evolutionary algorithms for the vertex cover problem. In: Proc. of CEC\u00a0\u201908, pp. 1563\u20131570. IEEE\u00a0Press (2008)","DOI":"10.1109\/CEC.2008.4631000"},{"key":"776_CR23","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.tcs.2015.01.002","volume":"605","author":"PS Oliveto","year":"2015","unstructured":"Oliveto, P.S., Witt, C.: Improved time complexity analysis of the simple genetic algorithm. Theor. Comput. Sci. 605, 21\u201341 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"776_CR24","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1002\/rsa.10085","volume":"23","author":"Y Ollivier","year":"2003","unstructured":"Ollivier, Y.: Rate of convergence of crossover operators. Random Struct. Algorithms 23, 58\u201372 (2003)","journal-title":"Random Struct. Algorithms"},{"key":"776_CR25","unstructured":"O\u2019Neill, M.E.: PCG: A family of simple fast space-efficient statistically good algorithms for random number generation. Tech. Rep. HMC-CS-2014-0905, Harvey Mudd College, Claremont, CA (2014)"},{"key":"776_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.artint.2013.09.002","volume":"204","author":"C Qian","year":"2013","unstructured":"Qian, C., Yang, Y., Zhou, Z.H.: An analysis on recombination in multi-objective evolutionary optimization. Artif. Intell. 204, 99\u2013119 (2013)","journal-title":"Artif. Intell."},{"key":"776_CR27","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<313::AID-RSA1>3.0.CO;2-W","volume":"12","author":"Y Rabani","year":"1998","unstructured":"Rabani, Y., Rabinovich, Y., Sinclair, A.: A computational view of population genetics. Random Struct. Algorithms 12, 313\u2013334 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"776_CR28","doi-asserted-by":"crossref","unstructured":"Rabinovich, Y., Sinclair, A., Wigderson, A.: Quadratic dynamical systems (preliminary version). In: Proc. of FOCS\u00a0\u201992, pp. 304\u2013313. IEEE Computer Society (1992)","DOI":"10.1109\/SFCS.1992.267761"},{"key":"776_CR29","doi-asserted-by":"crossref","unstructured":"Sudholt, D.: Crossover is provably essential for the Ising model on trees. In: Proc. of GECCO\u00a0\u201905, pp. 1161\u20131167. ACM Press (2005)","DOI":"10.1145\/1068009.1068202"},{"key":"776_CR30","doi-asserted-by":"publisher","first-page":"2511","DOI":"10.1016\/j.tcs.2009.03.003","volume":"410","author":"D Sudholt","year":"2009","unstructured":"Sudholt, D.: The impact of parametrization in memetic evolutionary algorithms. Theor. Comput. Sci. 410, 2511\u20132528 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"776_CR31","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1162\/EVCO_a_00171","volume":"25","author":"D Sudholt","year":"2017","unstructured":"Sudholt, D.: How crossover speeds up building block assembly in genetic algorithms. Evol. Comput. 25, 237\u2013274 (2017)","journal-title":"Evol. Comput."},{"key":"776_CR32","doi-asserted-by":"crossref","unstructured":"Sudholt, D., Witt, C.: Update strength in EDAs and ACO: how to avoid genetic drift. In: Proc. of GECCO\u00a0\u201916, pp. 61\u201368. ACM Press (2016)","DOI":"10.1145\/2908812.2908867"},{"key":"776_CR33","doi-asserted-by":"crossref","unstructured":"Sutton, A.M., Witt, C.: Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs. In: Proc. of GECCO\u00a0\u201919, pp. 1515\u20131522. ACM Press (2019)","DOI":"10.1145\/3321707.3321848"},{"key":"776_CR34","doi-asserted-by":"crossref","unstructured":"Watson, R.A., Jansen, T.: A building-block royal road where crossover is provably essential. In: Proc. of GECCO\u00a0\u201907, pp. 1452\u20131459. ACM Press (2007)","DOI":"10.1145\/1276958.1277224"},{"key":"776_CR35","doi-asserted-by":"crossref","unstructured":"Witt, C.: Population size vs. runtime of a simple EA. In: Proc. of CEC\u00a0\u201903, pp. 1996\u20132003. IEEE Press (2003)","DOI":"10.1109\/CEC.2003.1299918"},{"key":"776_CR36","first-page":"65","volume":"14","author":"C Witt","year":"2006","unstructured":"Witt, C.: Runtime analysis of the ($$\\mu $$+1) EA on simple pseudo-Boolean functions. Evol. Comput. 14, 65\u201386 (2006)","journal-title":"Evol. Comput."},{"key":"776_CR37","doi-asserted-by":"crossref","unstructured":"Witt, C.: Domino convergence: why one should hill-climb on linear functions. In: Proc. of GECCO\u00a0\u201918, pp. 1539\u20131546. ACM Press (2018)","DOI":"10.1145\/3205455.3205581"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00776-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00776-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00776-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T21:59:28Z","timestamp":1723845568000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00776-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,4]]},"references-count":37,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["776"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00776-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,11,4]]},"assertion":[{"value":"16 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}