{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:50Z","timestamp":1750219850207,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T00:00:00Z","timestamp":1689120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["R-22-ERCS-0003-01 pr"],"award-info":[{"award-number":["R-22-ERCS-0003-01 pr"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,15]]},"DOI":"10.1145\/3583131.3590482","type":"proceedings-article","created":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T19:40:19Z","timestamp":1689190819000},"page":"1565-1574","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4981-3227","authenticated-orcid":false,"given":"Carola","family":"Doerr","sequence":"first","affiliation":[{"name":"CNRS, Paris, France"},{"name":"Sorbonne Universit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7279-807X","authenticated-orcid":false,"given":"Duri Andrea","family":"Janett","sequence":"additional","affiliation":[{"name":"Department of Mathematics, ETH Zurich, Z\u00fcrich, Switzerland"},{"name":"Sorbonne Universit\u00e9, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0004-7629","authenticated-orcid":false,"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,12]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459377"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-00957-5"},{"key":"e_1_3_2_1_3_1","volume-title":"PPSN 2020, Leiden, The Netherlands, September 5--9, 2020, Proceedings, Part II. Springer, 545--559","author":"Antipov Denis","year":"2020","unstructured":"Denis Antipov and Benjamin Doerr . 2020 . Runtime analysis of a heavy-tailed (1 + (\u039b, \u039b)) genetic algorithm on jump functions. In Parallel Problem Solving from Nature-PPSN XVI: 16th International Conference , PPSN 2020, Leiden, The Netherlands, September 5--9, 2020, Proceedings, Part II. Springer, 545--559 . Denis Antipov and Benjamin Doerr. 2020. Runtime analysis of a heavy-tailed (1 + (\u039b, \u039b)) genetic algorithm on jump functions. In Parallel Problem Solving from Nature-PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5--9, 2020, Proceedings, Part II. Springer, 545--559."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469800"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450218.3477311"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459367"},{"key":"e_1_3_2_1_7_1","volume-title":"An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics. Algorithmica","author":"Bambury Henry","year":"2022","unstructured":"Henry Bambury , Antoine Bultel , and Benjamin Doerr . 2022. An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics. Algorithmica ( 2022 ), 1--32. Henry Bambury, Antoine Bultel, and Benjamin Doerr. 2022. An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics. Algorithmica (2022), 1--32."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460310.3460312"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00290"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC55065.2022.9870224"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58115-2_40"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459389"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450218.3477305"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2021.3068574"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.09.024"},{"key":"e_1_3_2_1_16_1","volume-title":"The Runtime of the Compact Genetic Algorithm on Jump Functions. Algorithmica 83 (10","author":"Doerr Benjamin","year":"2021","unstructured":"Benjamin Doerr . 2021. The Runtime of the Compact Genetic Algorithm on Jump Functions. Algorithmica 83 (10 2021 ), 1--49. Benjamin Doerr. 2021. The Runtime of the Compact Genetic Algorithm on Jump Functions. Algorithmica 83 (10 2021), 1--49."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.004"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.028"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00158"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.06.014"},{"key":"e_1_3_2_1_21_1","volume-title":"Runtime Analysis for Permutation-based Evolutionary Algorithms. arXiv preprint arXiv:2207.04045","author":"Doerr Benjamin","year":"2022","unstructured":"Benjamin Doerr , Yassine Ghannane , and Marouane Ibn Brahim . 2022. Runtime Analysis for Permutation-based Evolutionary Algorithms. arXiv preprint arXiv:2207.04045 ( 2022 ). Benjamin Doerr, Yassine Ghannane, and Marouane Ibn Brahim. 2022. Runtime Analysis for Permutation-based Evolutionary Algorithms. arXiv preprint arXiv:2207.04045 (2022)."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512290.3528868"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1967654.1967669"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2010.5586097"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9622-x"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.10.039"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3071178.3071301"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472304"},{"key":"e_1_3_2_1_29_1","volume-title":"PPSN 2022, Dortmund, Germany, September 10--14, 2022, Proceedings, Part II. Springer, 399--412","author":"Doerr Benjamin","year":"2022","unstructured":"Benjamin Doerr and Zhongdi Qu . 2022 . A first runtime analysis of the NSGA-II on a multimodal problem. In Parallel Problem Solving from Nature-PPSN XVII: 17th International Conference , PPSN 2022, Dortmund, Germany, September 10--14, 2022, Proceedings, Part II. Springer, 399--412 . Benjamin Doerr and Zhongdi Qu. 2022. A first runtime analysis of the NSGA-II on a multimodal problem. In Parallel Problem Solving from Nature-PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10--14, 2022, Proceedings, Part II. Springer, 399--412."},{"key":"e_1_3_2_1_30_1","volume-title":"Stagnation detection meets fast mutation. Theoretical Computer Science","author":"Doerr Benjamin","year":"2022","unstructured":"Benjamin Doerr and Amirhossein Rajabi . 2022. Stagnation detection meets fast mutation. Theoretical Computer Science ( 2022 ). Benjamin Doerr and Amirhossein Rajabi. 2022. Stagnation detection meets fast mutation. Theoretical Computer Science (2022)."},{"key":"e_1_3_2_1_31_1","volume-title":"Artificial Evolution: 10th International Conference","author":"Doerr Benjamin","year":"2011","unstructured":"Benjamin Doerr and Carola Winzen . 2012. Black-box complexity: Breaking the O (n log n) barrier of LeadingOnes . In Artificial Evolution: 10th International Conference , Evolution Artificielle, EA 2011 , Angers, France, October 24--26, 2011, Revised Selected Papers 10. Springer , 205--216. Benjamin Doerr and Carola Winzen. 2012. Black-box complexity: Breaking the O (n log n) barrier of LeadingOnes. In Artificial Evolution: 10th International Conference, Evolution Artificielle, EA 2011, Angers, France, October 24--26, 2011, Revised Selected Papers 10. Springer, 205--216."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449726.3462719"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2302.12338"},{"key":"e_1_3_2_1_35_1","volume-title":"Sander Van Rijn, and Thomas B\u00e4ck","author":"Doerr Carola","year":"2018","unstructured":"Carola Doerr , Hao Wang , Furong Ye , Sander Van Rijn, and Thomas B\u00e4ck . 2018 . IOHprofiler : A benchmarking and profiling tool for iterative optimization heuristics. arXiv preprint arXiv:1810.05281 (2018). Carola Doerr, Hao Wang, Furong Ye, Sander Van Rijn, and Thomas B\u00e4ck. 2018. IOHprofiler: A benchmarking and profiling tool for iterative optimization heuristics. arXiv preprint arXiv:1810.05281 (2018)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1177-z"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings, Part I 15","author":"Friedrich Tobias","year":"2018","unstructured":"Tobias Friedrich , Andreas G\u00f6bel , Francesco Quinzan , and Markus Wagner . 2018 . Heavy-tailed mutation operators in single-objective combinatorial optimization. In Parallel Problem Solving from Nature-PPSN XV: 15th International Conference, Coimbra, Portugal, September 8--12, 2018 , Proceedings, Part I 15 . Springer, 134--145. Tobias Friedrich, Andreas G\u00f6bel, Francesco Quinzan, and Markus Wagner. 2018. Heavy-tailed mutation operators in single-objective combinatorial optimization. In Parallel Problem Solving from Nature-PPSN XV: 15th International Conference, Coimbra, Portugal, September 8--12, 2018, Proceedings, Part I 15. Springer, 134--145."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3205455.3205515"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings 10","author":"J\u00e4gersk\u00fcpper Jens","year":"2008","unstructured":"Jens J\u00e4gersk\u00fcpper . 2008 . A blend of Markov-chain and drift analysis. In Parallel Problem Solving from Nature-PPSN X: 10th International Conference, Dortmund, Germany, September 13--17, 2008 . Proceedings 10 . Springer, 41--51. Jens J\u00e4gersk\u00fcpper. 2008. A blend of Markov-chain and drift analysis. In Parallel Problem Solving from Nature-PPSN X: 10th International Conference, Dortmund, Germany, September 13--17, 2008. Proceedings 10. Springer, 41--51."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS51168.2021.9636503"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2019.2954234"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9616-8"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2019.2917014"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2725494.2725506"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3067695.3082507"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512290.3528755"},{"key":"e_1_3_2_1_47_1","volume-title":"PPSN 2022, Dortmund, Germany, September 10--14, 2022, Proceedings, Part I. Springer, 294--307","author":"Neumann Aneta","year":"2022","unstructured":"Aneta Neumann , Yue Xie , and Frank Neumann . 2022 . Evolutionary algorithms for limiting the effect of uncertainty for the knapsack problem with stochastic profits. In Parallel Problem Solving from Nature-PPSN XVII: 17th International Conference , PPSN 2022, Dortmund, Germany, September 10--14, 2022, Proceedings, Part I. Springer, 294--307 . Aneta Neumann, Yue Xie, and Frank Neumann. 2022. Evolutionary algorithms for limiting the effect of uncertainty for the knapsack problem with stochastic profits. In Parallel Problem Solving from Nature-PPSN XVII: 17th International Conference, PPSN 2022, Dortmund, Germany, September 10--14, 2022, Proceedings, Part I. Springer, 294--307."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.05.011"},{"key":"e_1_3_2_1_49_1","volume-title":"Asynchronous Evolutionary Algorithm for Finding Backdoors in Boolean Satisfiability. In 2022 IEEE Congress on Evolutionary Computation (CEC). IEEE, 1--8.","author":"Pavlenko Artem","year":"2022","unstructured":"Artem Pavlenko , Daniil Chivilikhin , and Alexander Semenov . 2022 . Asynchronous Evolutionary Algorithm for Finding Backdoors in Boolean Satisfiability. In 2022 IEEE Congress on Evolutionary Computation (CEC). IEEE, 1--8. Artem Pavlenko, Daniil Chivilikhin, and Alexander Semenov. 2022. Asynchronous Evolutionary Algorithm for Finding Backdoors in Boolean Satisfiability. In 2022 IEEE Congress on Evolutionary Computation (CEC). IEEE, 1--8."},{"key":"e_1_3_2_1_50_1","volume-title":"Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations. Natural Computing","author":"Quinzan Francesco","year":"2021","unstructured":"Francesco Quinzan , Andreas G\u00f6bel , Markus Wagner , and Tobias Friedrich . 2021. Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations. Natural Computing ( 2021 ), 1--15. Francesco Quinzan, Andreas G\u00f6bel, Markus Wagner, and Tobias Friedrich. 2021. Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations. Natural Computing (2021), 1--15."},{"key":"e_1_3_2_1_51_1","volume-title":"27th International Conference on Principles and Practice of Constraint Programming (CP","author":"Semenov Alexander","year":"2021","unstructured":"Alexander Semenov , Daniil Chivilikhin , Artem Pavlenko , Ilya Otpuschennikov , Vladimir Ulyantsev , and Alexey Ignatiev . 2021 . Evaluating the hardness of SAT instances using evolutionary optimization algorithms . In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. Alexander Semenov, Daniil Chivilikhin, Artem Pavlenko, Ilya Otpuschennikov, Vladimir Ulyantsev, and Alexey Ignatiev. 2021. Evaluating the hardness of SAT instances using evolutionary optimization algorithms. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2012.2202241"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000600"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.09.013"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-95957-3_4"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2019.8790107"},{"key":"e_1_3_2_1_57_1","volume-title":"PPSN 2020, Leiden, The Netherlands, September 5--9, 2020, Proceedings, Part II. Springer, 699--713","author":"Ye Furong","year":"2020","unstructured":"Furong Ye , Hao Wang , Carola Doerr , and Thomas B\u00e4ck . 2020 . Benchmarking a genetic algorithm with configurable crossover probability. In Parallel Problem Solving from Nature-PPSN XVI: 16th International Conference , PPSN 2020, Leiden, The Netherlands, September 5--9, 2020, Proceedings, Part II. Springer, 699--713 . Furong Ye, Hao Wang, Carola Doerr, and Thomas B\u00e4ck. 2020. Benchmarking a genetic algorithm with configurable crossover probability. In Parallel Problem Solving from Nature-PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5--9, 2020, Proceedings, Part II. Springer, 699--713."}],"event":{"name":"GECCO '23: Genetic and Evolutionary Computation Conference","sponsor":["SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation"],"location":"Lisbon Portugal","acronym":"GECCO '23"},"container-title":["Proceedings of the Genetic and Evolutionary Computation Conference"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583131.3590482","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583131.3590482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:04Z","timestamp":1750178824000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583131.3590482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,12]]},"references-count":57,"alternative-id":["10.1145\/3583131.3590482","10.1145\/3583131"],"URL":"https:\/\/doi.org\/10.1145\/3583131.3590482","relation":{},"subject":[],"published":{"date-parts":[[2023,7,12]]},"assertion":[{"value":"2023-07-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}