{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T06:15:42Z","timestamp":1780467342602,"version":"3.54.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,3,21]],"date-time":"2017-03-21T00:00:00Z","timestamp":1490054400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"FMJH Program Gaspard Monge in optimization and operation research, supported by Electricit\u00e9 de France"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s00453-017-0304-6","type":"journal-article","created":{"date-parts":[[2017,3,21]],"date-time":"2017-03-21T23:47:32Z","timestamp":1490140052000},"page":"1579-1603","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["The $$(1+1)$$ ( 1 + 1 ) Elitist Black-Box Complexity of LeadingOnes"],"prefix":"10.1007","volume":"80","author":[{"given":"Carola","family":"Doerr","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0004-7629","authenticated-orcid":false,"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,3,21]]},"reference":[{"key":"304_CR1","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms-Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday","author":"P Afshani","year":"2013","unstructured":"Afshani, P., Agrawal, M., Doerr, B., Doerr, C., Larsen, K.G., Mehlhorn, K.: The query complexity of finding a hidden permutation. Space-Efficient Data Structures, Streams, and Algorithms-Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday. Lecture Notes in Computer Science, vol. 8066, pp. 1\u201311. Springer, New York (2013)"},{"key":"304_CR2","doi-asserted-by":"crossref","unstructured":"B\u00f6ttcher, S., Doerr, B., Neumann, F.: Optimal fixed and adaptive mutation rates for the LeadingOnes problem. In: Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN\u201910), pp. 1\u201310. Springer (2010)","DOI":"10.1007\/978-3-642-15844-5_1"},{"key":"304_CR3","doi-asserted-by":"crossref","unstructured":"Doerr, B., Doerr, C., Ebel, F.: Lessons from the black-box: Fast crossover-based genetic algorithms. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201913), pp. 781\u2013788. ACM (2013)","DOI":"10.1145\/2463372.2463480"},{"key":"304_CR4","doi-asserted-by":"crossref","unstructured":"Doerr, B., Johannsen, D., K\u00f6tzing, T., Lehre, P.K., Wagner, M., Winzen, C.: Faster black-box algorithms through higher arity operators. In: Proceedings of Foundations of Genetic Algorithms (FOGA\u201911), pp. 163\u2013172. ACM (2011)","DOI":"10.1145\/1967654.1967669"},{"key":"304_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/978-3-642-35533-2_18","volume-title":"Artificial Evolution (EA\u201911), Revised Selected Papers","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Winzen, C.: Black-box complexity: breaking the $$O(n \\log n)$$ O ( n log n ) barrier of LeadingOnes. Artificial Evolution (EA\u201911), Revised Selected Papers. Lecture Notes in Computer Science, vol. 7401, pp. 205\u2013216. Springer, New York (2012)"},{"key":"304_CR6","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1007\/s00224-012-9438-8","volume":"55","author":"B Doerr","year":"2014","unstructured":"Doerr, B., Winzen, C.: Playing mastermind with constant-size memory. Theory Comput. Syst. 55, 658\u2013684 (2014)","journal-title":"Theory Comput. Syst."},{"key":"304_CR7","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1007\/s00453-012-9684-9","volume":"68","author":"B Doerr","year":"2014","unstructured":"Doerr, B., Winzen, C.: Ranking-based black-box complexity. Algorithmica 68, 571\u2013609 (2014)","journal-title":"Algorithmica"},{"key":"304_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, C., Lengler, J.: Elitist black-box models: analyzing the impact of elitist selection on the performance of evolutionary algorithms. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201915), pp. 839\u2013846. ACM (2015)","DOI":"10.1145\/2739480.2754654"},{"key":"304_CR9","doi-asserted-by":"crossref","unstructured":"Doerr, C., Lengler, J.: OneMax in black-box models with several restrictions. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201915), pp. 1431\u20131438. ACM (2015)","DOI":"10.1145\/2739480.2754678"},{"key":"304_CR10","doi-asserted-by":"crossref","unstructured":"Doerr, C., Lengler, J.: The $$(1+1)$$ ( 1 + 1 ) elitist black-box complexity of LeadingOnes. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201916), pp. 1131\u20131138. ACM (2016)","DOI":"10.1145\/2908812.2908922"},{"key":"304_CR11","doi-asserted-by":"crossref","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.: On the analysis of the $$(1+1)$$ ( 1 + 1 ) evolutionary algorithm. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"304_CR12","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s00224-004-1177-z","volume":"39","author":"S Droste","year":"2006","unstructured":"Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39, 525\u2013544 (2006)","journal-title":"Theory Comput. Syst."},{"key":"304_CR13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1239\/jap\/1110381369","volume":"42","author":"V Ladret","year":"2005","unstructured":"Ladret, V.: Asymptotic hitting time for a simple evolutionary model of protein folding. J. Appl. Prob. 42, 39\u201351 (2005)","journal-title":"J. Appl. Prob."},{"key":"304_CR14","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1007\/s00453-012-9616-8","volume":"64","author":"PK Lehre","year":"2012","unstructured":"Lehre, P.K., Witt, C.: Black-box search by unbiased variation. Algorithmica 64, 623\u2013642 (2012)","journal-title":"Algorithmica"},{"key":"304_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"304_CR16","unstructured":"M\u00fchlenbein, H.: How genetic algorithms really work: mutation and hillclimbing. In: Proceedings of the 2nd International Conference on Parallel Problem Solving from Nature (PPSN\u201992), pp. 15\u201326. Elsevier (1992)"},{"key":"304_CR17","volume-title":"Convergence Properties of Evolutionary Algorithms","author":"G Rudolph","year":"1997","unstructured":"Rudolph, G.: Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kova\u010d, Hamburg (1997)"},{"key":"304_CR18","doi-asserted-by":"crossref","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":"304_CR19","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Probabilistic computations: toward a unified measure of complexity. In: Proceedings of Foundations of Computer Science (FOCS\u201977), pp. 222\u2013227. IEEE (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0304-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0304-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0304-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T21:53:07Z","timestamp":1568929987000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0304-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,21]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["304"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0304-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,21]]}}}