{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T06:01:48Z","timestamp":1783749708770,"version":"3.55.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T00:00:00Z","timestamp":1635897600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T00:00:00Z","timestamp":1635897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-LABX-0056-LMH"],"award-info":[{"award-number":["ANR-11-LABX-0056-LMH"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002261","name":"\u0420\u043e\u0441\u0441\u0438\u0439\u0441\u043a\u0438\u0439 \u0424\u043e\u043d\u0434 \u0424\u0443\u043d\u0434\u0430\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0418\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u0439","doi-asserted-by":"publisher","award":["20-51-15009"],"award-info":[{"award-number":["20-51-15009"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00453-021-00881-0","type":"journal-article","created":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T07:03:44Z","timestamp":1635923024000},"page":"1762-1793","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Fixed-Target Runtime Analysis"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7120-8824","authenticated-orcid":false,"given":"Maxim","family":"Buzdalov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carola","family":"Doerr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dmitry","family":"Vinokurov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,11,3]]},"reference":[{"key":"881_CR1","doi-asserted-by":"crossref","unstructured":"Antipov, D., Buzdalov, M., Doerr, B.: First steps towards a runtime analysis when starting with a good solution. In: Parallel Problem Solving from Nature, PPSN 2020, pp. 560\u2013573. Springer (2020)","DOI":"10.1007\/978-3-030-58115-2_39"},{"key":"881_CR2","doi-asserted-by":"crossref","unstructured":"B\u00f6ttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In: Parallel Problem Solving from Nature, PPSN 2010, pp. 1\u201310. Springer (2010)","DOI":"10.1007\/978-3-642-15844-5_1"},{"key":"881_CR3","doi-asserted-by":"crossref","unstructured":"Buskulic, N., Doerr, C.: Maximizing drift is not optimal for solving OneMax. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2019, Prague, Czech Republic, July 13\u201317, 2019, pp. 425\u2013426 (2019)","DOI":"10.1145\/3319619.3321952"},{"key":"881_CR4","doi-asserted-by":"crossref","unstructured":"Buzdalov, M., Doerr, B., Doerr, C., Vinokurov, D.: Fixed-target runtime analysis. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 1295\u20131303. ACM (2020)","DOI":"10.1145\/3377930.3390184"},{"key":"881_CR5","unstructured":"Carvalho Pinto, E., Doerr, C.: Towards a more practice-aware runtime analysis of evolutionary algorithms. arXiv:1812.00493 (2018)"},{"key":"881_CR6","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/TEVC.2017.2753538","volume":"22","author":"D Corus","year":"2018","unstructured":"Corus, D., Dang, D., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. IEEE Trans. Evol. Comput. 22, 707\u2013719 (2018)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"881_CR7","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2018.09.024","volume":"773","author":"B Doerr","year":"2019","unstructured":"Doerr, B.: Analyzing randomized search heuristics via stochastic domination. Theoret. Comput. Sci. 773, 115\u2013137 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"881_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, B.: A tight runtime analysis for the cGA on jump functions: EDAs can cross fitness valleys at no extra cost. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1488\u20131496. ACM (2019)","DOI":"10.1145\/3321707.3321747"},{"key":"881_CR9","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00453-015-0019-5","volume":"75","author":"B Doerr","year":"2016","unstructured":"Doerr, B., Doerr, C.: The impact of random initialization on the runtime of randomized search heuristics. Algorithmica 75, 529\u2013553 (2016)","journal-title":"Algorithmica"},{"key":"881_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2014.11.028","volume":"567","author":"B Doerr","year":"2015","unstructured":"Doerr, B., Doerr, C., Ebel, F.: From black-box complexity to designing new genetic algorithms. Theoret. Comput. Sci. 567, 87\u2013104 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"881_CR11","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C., Yang, J.: $$k$$-bit mutation with self-adjusting $$k$$ outperforms standard bit mutation. In: Parallel Problem Solving from Nature, PPSN 2016, pp. 824\u2013834. Springer (2016)","DOI":"10.1007\/978-3-319-45823-6_77"},{"key":"881_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C., Yang, J.: Optimal parameter choices via precise black-box analysis. In: Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 1123\u20131130. ACM (2016)","DOI":"10.1145\/2908812.2908950"},{"key":"881_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.06.014","volume":"801","author":"B Doerr","year":"2020","unstructured":"Doerr, B., Doerr, C., Yang, J.: Optimal parameter choices via precise black-box analysis. Theoret. Comput. Sci. 801, 1\u201334 (2020)","journal-title":"Theoret. Comput. Sci."},{"key":"881_CR14","doi-asserted-by":"crossref","unstructured":"Doerr, B., Fouz, M., Witt, C.: Sharp bounds by probability-generating functions and variable drift. In: Genetic and Evolutionary Computation Conference, GECCO 2011, pp. 2083\u20132090. ACM (2011)","DOI":"10.1145\/2001576.2001856"},{"key":"881_CR15","doi-asserted-by":"crossref","unstructured":"Doerr, B., Goldberg, L.: Drift analysis with tail bounds. In: Parallel Problem Solving from Nature, PPSN 2010, Lecture Notes in Computer Science, vol. 6238, pp. 174\u2013183. Springer (2010)","DOI":"10.1007\/978-3-642-15844-5_18"},{"key":"881_CR16","doi-asserted-by":"crossref","unstructured":"Doerr, B., Jansen, T., Witt, C., Zarges, C.: A method to derive fixed budget results from expected optimisation times. In: Genetic and Evolutionary Computation Conference, GECCO 2013, pp. 1581\u20131588. ACM (2013)","DOI":"10.1145\/2463372.2463565"},{"key":"881_CR17","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":"881_CR18","doi-asserted-by":"crossref","unstructured":"Doerr, B., K\u00f6tzing, T.: Multiplicative up-drift. In: Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 1470\u20131478. ACM (2019)","DOI":"10.1145\/3321707.3321819"},{"key":"881_CR19","doi-asserted-by":"crossref","unstructured":"Doerr, B., K\u00f6tzing, T.: Lower bounds from fitness levels made easy. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 1142\u20131150. ACM (2021)","DOI":"10.1145\/3449639.3459352"},{"key":"881_CR20","doi-asserted-by":"crossref","unstructured":"Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 777\u2013784. ACM (2017)","DOI":"10.1145\/3071178.3071301"},{"key":"881_CR21","volume-title":"Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization","year":"2020","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation\u2014Recent Developments in Discrete Optimization. Springer, New York (2020)"},{"key":"881_CR22","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/s00453-016-0168-1","volume":"78","author":"C Doerr","year":"2017","unstructured":"Doerr, C., Lengler, J.: OneMax in black-box models with several restrictions. Algorithmica 78, 610\u2013640 (2017)","journal-title":"Algorithmica"},{"key":"881_CR23","unstructured":"Doerr, C., Wang, H., Ye, F., van Rijn, S., B\u00e4ck, T.: IOHprofiler: a benchmarking and profiling tool for iterative optimization heuristics. https:\/\/arxiv.org\/abs\/1810.05281 (2018). IOHprofiler is available at https:\/\/github.com\/IOHprofiler"},{"key":"881_CR24","doi-asserted-by":"crossref","unstructured":"Doerr, C., Ye, F., van Rijn, S., Wang, H., B\u00e4ck, T.: Towards a theory-guided benchmarking suite for discrete black-box optimization heuristics: profiling $$(1+\\lambda )$$ EA variants on OneMax and LeadingOnes. In: Genetic and Evolutionary Computation Conference, pp. 951\u2013958. ACM (2018)","DOI":"10.1145\/3205455.3205621"},{"key":"881_CR25","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2020.1808977","author":"N Hansen","year":"2020","unstructured":"Hansen, N., Auger, A., Ros, R., Mersmann, O., Tu\u0161ar, T., Brockhoff, D.: COCO: a platform for comparing continuous optimizers in a black-box setting. Optim. Methods Softw. (2020). https:\/\/doi.org\/10.1080\/10556788.2020.1808977","journal-title":"Optim. Methods Softw."},{"key":"881_CR26","doi-asserted-by":"crossref","unstructured":"He, J., Jansen, T., Zarges, C.: Unlimited budget analysis. In: Genetic and Evolutionary Computation Conference Companion, GECCO 2019, pp. 427\u2013428 (2019)","DOI":"10.1145\/3319619.3322009"},{"key":"881_CR27","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0004-3702(01)00058-3","volume":"127","author":"J He","year":"2001","unstructured":"He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127, 51\u201381 (2001)","journal-title":"Artif. Intell."},{"key":"881_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective. Springer, New York (2013)"},{"key":"881_CR29","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.: On the analysis of a dynamic evolutionary algorithm. J. Discrete Algorithms 4, 181\u2013199 (2006)","journal-title":"J. Discrete Algorithms"},{"key":"881_CR30","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.tcs.2013.06.007","volume":"545","author":"T Jansen","year":"2014","unstructured":"Jansen, T., Zarges, C.: Performance analysis of randomised search heuristics operating with a fixed budget. Theoret. Comput. Sci. 545, 39\u201358 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"881_CR31","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1109\/TEVC.2014.2349160","volume":"18","author":"T Jansen","year":"2014","unstructured":"Jansen, T., Zarges, C.: Reevaluating immune-inspired hypermutations using the fixed budget perspective. IEEE Trans. Evol. Comput. 18, 674\u2013688 (2014)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"881_CR32","unstructured":"Johannsen, D.: Random combinatorial structures and randomized search heuristics. Ph.D. thesis, Universit\u00e4t des Saarlandes (2010)"},{"key":"881_CR33","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","volume":"75","author":"T K\u00f6tzing","year":"2016","unstructured":"K\u00f6tzing, T.: Concentration of first hitting times under additive drift. Algorithmica 75, 490\u2013506 (2016)","journal-title":"Algorithmica"},{"key":"881_CR34","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2019.08.021","volume":"796","author":"T K\u00f6tzing","year":"2019","unstructured":"K\u00f6tzing, T., Krejca, M.: First-hitting times under drift. Theoret. Comput. Sci. 796, 51\u201369 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"881_CR35","doi-asserted-by":"crossref","unstructured":"K\u00f6tzing, T., Witt, C.: Improved fixed-budget results via drift analysis. In: Parallel Problem Solving from Nature, PPSN 2020, pp. 648\u2013660. Springer (2020)","DOI":"10.1007\/978-3-030-58115-2_45"},{"key":"881_CR36","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.1109\/TEVC.2019.2954234","volume":"24","author":"PK Lehre","year":"2020","unstructured":"Lehre, P.K., Sudholt, D.: Parallel black-box complexity with tail bounds. IEEE Trans. Evol. Comput. 24, 1010\u20131024 (2020)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"4","key":"881_CR37","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1017\/S0963548320000565","volume":"30","author":"PK Lehre","year":"2021","unstructured":"Lehre, P.K., Witt, C.: Tail bounds on hitting times of randomized search heuristics using variable drift analysis. Comb. Probab. Comput. 30(4), 550\u2013569 (2021)","journal-title":"Comb. Probab. Comput."},{"key":"881_CR38","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"J Lengler","year":"2020","unstructured":"Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 89\u2013131. Springer, New York (2020)"},{"key":"881_CR39","doi-asserted-by":"crossref","unstructured":"Lengler, J., Spooner, N.: Fixed budget performance of the (1+1) EA on linear functions. In: Foundations of Genetic Algorithms, FOGA 2015, pp. 52\u201361. ACM (2015)","DOI":"10.1145\/2725494.2725506"},{"key":"881_CR40","doi-asserted-by":"crossref","unstructured":"Lengler, J., Zou, X.: Exponential slowdown for larger populations: the $$(\\mu +1)$$-EA on monotone functions. In: Foundations of Genetic Algorithms, FOGA 2019, pp. 87\u2013101. ACM (2019)","DOI":"10.1145\/3299904.3340309"},{"key":"881_CR41","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1108\/17563780910959893","volume":"2","author":"B Mitavskiy","year":"2009","unstructured":"Mitavskiy, B., Rowe, J.E., Cannings, C.: Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Int. J. Intell. Comput. Cybern. 2, 243\u2013284 (2009)","journal-title":"Int. J. Intell. Comput. Cybern."},{"issue":"4","key":"881_CR42","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1162\/evco_a_00199","volume":"25","author":"S Nallaperuma","year":"2017","unstructured":"Nallaperuma, S., Neumann, F., Sudholt, D.: Expected fitness gains of randomized search heuristics for the traveling salesperson problem. Evol. Comput. 25(4), 673\u2013705 (2017)","journal-title":"Evol. Comput."},{"key":"881_CR43","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2006.11.002","volume":"378","author":"F Neumann","year":"2007","unstructured":"Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoret. Comput. Sci. 378, 32\u201340 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"881_CR44","doi-asserted-by":"publisher","first-page":"3130","DOI":"10.1016\/j.disc.2007.03.052","volume":"307","author":"MZ Spivey","year":"2007","unstructured":"Spivey, M.Z.: Combinatorial sums and finite differences. Discrete Math. 307, 3130\u20133146 (2007)","journal-title":"Discrete Math."},{"key":"881_CR45","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TEVC.2012.2202241","volume":"17","author":"D Sudholt","year":"2013","unstructured":"Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17, 418\u2013435 (2013)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"881_CR46","doi-asserted-by":"crossref","unstructured":"Vinokurov, D., Buzdalov, M., Buzdalova, A., Doerr, B., Doerr, C.: Fixed-target runtime analysis of the (1+1) EA with resampling. In: Genetic and Evolutionary Computation Conference Companion, GECCO 2019, pp. 2068\u20132071 (2019)","DOI":"10.1145\/3319619.3326906"},{"key":"881_CR47","first-page":"349","volume-title":"Evolutionary Optimization","author":"I Wegener","year":"2002","unstructured":"Wegener, I.: Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In: Sarker, R., Mohammadian, M., Yao, X. (eds.) Evolutionary Optimization, pp. 349\u2013369. Kluwer, Dordrecht (2002)"},{"key":"881_CR48","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":"881_CR49","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","volume":"22","author":"C Witt","year":"2013","unstructured":"Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combin. Probab. Comput. 22, 294\u2013318 (2013)","journal-title":"Combin. Probab. Comput."},{"key":"881_CR50","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.ipl.2013.09.013","volume":"114","author":"C Witt","year":"2014","unstructured":"Witt, C.: Fitness levels with tail bounds for the analysis of randomized search heuristics. Inf. Process. Lett. 114, 38\u201341 (2014)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00881-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00881-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00881-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T08:33:43Z","timestamp":1653726823000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00881-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,3]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["881"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00881-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,3]]},"assertion":[{"value":"22 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}