{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:45Z","timestamp":1750219785641,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,15]],"date-time":"2023-07-15T00:00:00Z","timestamp":1689379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Agence National de Recherche","award":["ANR-11-LABX-0056-LMH"],"award-info":[{"award-number":["ANR-11-LABX-0056-LMH"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,15]]},"DOI":"10.1145\/3583133.3595845","type":"proceedings-article","created":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T23:30:33Z","timestamp":1690241433000},"page":"19-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Hot off the Press: Runtime Analysis for the NSGA-II - Provable Speed-Ups From Crossover"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5283-4208","authenticated-orcid":false,"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[{"name":"Ecole Polytechnique, Palaiseau, France"},{"name":"Laboratoire d'Informatique (LIX), Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7789-712X","authenticated-orcid":false,"given":"Zhongdi","family":"Qu","sequence":"additional","affiliation":[{"name":"Ecole Polytechnique, Palaiseau, France"},{"name":"Laboratoire d'Informatique (LIX), Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00907-7"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics. World Scientific Publishing.  Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics. World Scientific Publishing.","DOI":"10.1142\/7438"},{"key":"e_1_3_2_1_3_1","volume-title":"PPSN","author":"Bian Chao","year":"2022","unstructured":"Chao Bian and Chao Qian . 2022 . Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection. In Parallel Problem Solving From Nature , PPSN 2022. Springer, 428--441. Chao Bian and Chao Qian. 2022. Better running time of the non-dominated sorting genetic algorithm II (NSGA-II) by using stochastic tournament selection. In Parallel Problem Solving From Nature, PPSN 2022. Springer, 428--441."},{"key":"e_1_3_2_1_4_1","volume-title":"Genetic and Evolutionary Computation Conference, GECCO","author":"Dang Duc-Cuong","year":"2016","unstructured":"Duc-Cuong Dang , Tobias Friedrich , Timo K\u00f6tzing , Martin S. Krejca , Per Kristian Lehre , Pietro S. Oliveto , Dirk Sudholt , and Andrew M. Sutton . 2016. Escaping local optima with diversity mechanisms and crossover . In Genetic and Evolutionary Computation Conference, GECCO 2016 . ACM, 645--652. Duc-Cuong Dang, Tobias Friedrich, Timo K\u00f6tzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2016. Escaping local optima with diversity mechanisms and crossover. In Genetic and Evolutionary Computation Conference, GECCO 2016. ACM, 645--652."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2724201"},{"key":"e_1_3_2_1_6_1","volume-title":"Conference on Artificial Intelligence, AAAI","author":"Dang Duc-Cuong","year":"2023","unstructured":"Duc-Cuong Dang , Andre Opris , Bahare Salehi , and Dirk Sudholt . 2023 . A proof that using crossover can guarantee exponential speed-ups in evolutionary multiobjective optimisation . In Conference on Artificial Intelligence, AAAI 2023. AAAI Press. To appear. Duc-Cuong Dang, Andre Opris, Bahare Salehi, and Dirk Sudholt. 2023. A proof that using crossover can guarantee exponential speed-ups in evolutionary multiobjective optimisation. In Conference on Artificial Intelligence, AAAI 2023. AAAI Press. To appear."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/4235.996017"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.028"},{"key":"e_1_3_2_1_9_1","volume-title":"Krejca","author":"Doerr Benjamin","year":"2022","unstructured":"Benjamin Doerr , Aymen Echarghaoui , Mohammed Jamal , and Martin S . Krejca . 2022 . Lasting Diversity and Superior Runtime Guarantees for the (\u03bc + 1) Genetic Algorithm. CoRR abs\/2302.12570 (2022). arXiv:2302.12570 Benjamin Doerr, Aymen Echarghaoui, Mohammed Jamal, and Martin S. Krejca. 2022. Lasting Diversity and Superior Runtime Guarantees for the (\u03bc + 1) Genetic Algorithm. CoRR abs\/2302.12570 (2022). arXiv:2302.12570"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.035"},{"key":"e_1_3_2_1_11_1","volume-title":"PPSN","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 2022. 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 2022. Springer, 399--412."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i10.26462"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i10.26461"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449726.3462719"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33012296"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0940-2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001711"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-010-0610-2"},{"key":"e_1_3_2_1_19_1","volume-title":"Holland","author":"Mitchell Melanie","year":"1992","unstructured":"Melanie Mitchell , Stephanie Forrest , and John H . Holland . 1992 . The royal road for genetic algorithms: fitness landscapes and GA performance. In Proc. of the First European Conference on Artificial Life. MIT Press , 245--254. Melanie Mitchell, Stephanie Forrest, and John H. Holland. 1992. The royal road for genetic algorithms: fitness landscapes and GA performance. In Proc. of the First European Conference on Artificial Life. MIT Press, 245--254."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15844-5_67"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.09.002"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1068009.1068202"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00809-8"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512290.3528847"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i9.21283"}],"event":{"name":"GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation","sponsor":["SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation"],"location":"Lisbon Portugal","acronym":"GECCO '23 Companion"},"container-title":["Proceedings of the Companion Conference on Genetic and Evolutionary Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583133.3595845","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583133.3595845","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:50Z","timestamp":1750178270000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583133.3595845"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,15]]},"references-count":25,"alternative-id":["10.1145\/3583133.3595845","10.1145\/3583133"],"URL":"https:\/\/doi.org\/10.1145\/3583133.3595845","relation":{},"subject":[],"published":{"date-parts":[[2023,7,15]]},"assertion":[{"value":"2023-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}