{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T18:11:46Z","timestamp":1763057506369},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,1,23]],"date-time":"2010-01-23T00:00:00Z","timestamp":1264204800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,3]]},"DOI":"10.1007\/s00453-010-9391-3","type":"journal-article","created":{"date-parts":[[2010,1,22]],"date-time":"2010-01-22T15:12:43Z","timestamp":1264173163000},"page":"387-408","source":"Crossref","is-referenced-by-count":19,"title":["Lower Bounds for Comparison Based Evolution Strategies Using VC-dimension and Sign Patterns"],"prefix":"10.1007","volume":"59","author":[{"given":"Herv\u00e9","family":"Fournier","sequence":"first","affiliation":[]},{"given":"Olivier","family":"Teytaud","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,1,23]]},"reference":[{"key":"9391_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/11513575_12","volume-title":"Foundations of Genetic Algorithms\u00a08","author":"D.V. Arnold","year":"2005","unstructured":"Arnold, D.V.: Optimal weighted recombination. In: Foundations of Genetic Algorithms\u00a08. Lecture Notes in Computer Science, vol. 3469, pp. 215\u2013237. Springer, Berlin (2005)"},{"issue":"1\u20133","key":"9391_CR2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.tcs.2004.11.017","volume":"334","author":"A. Auger","year":"2005","unstructured":"Auger, A.: Convergence results for (1,\u03bb)-SA-ES using the theory of \u03c6-irreducible Markov chains. Theor. Comput. Sci. 334(1\u20133), 35\u201369 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9391_CR3","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1145\/1068009.1068154","volume-title":"GECCO\u201905: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation","author":"A. Auger","year":"2005","unstructured":"Auger, A., Schoenauer, M., Teytaud, O.: Local and global order 3\/2 convergence of a surrogate evolutionary algorithm. In: GECCO\u201905: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, pp. 857\u2013864. ACM, New York (2005)"},{"key":"9391_CR4","first-page":"92","volume-title":"Proceedings of the Fourth International Conference on Genetic Algorithms","author":"T. B\u00e4ck","year":"1991","unstructured":"B\u00e4ck, T., Hoffmeister, F., Schwefel, H.-P.: Extended selection mechanisms in genetic algorithms. In: Belew, R.K., Booker, L.B. (eds.) Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 92\u201399. Morgan Kaufmann, San Mateo (1991)"},{"key":"9391_CR5","first-page":"14","volume-title":"Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application","author":"J.E. Baker","year":"1987","unstructured":"Baker, J.E.: Reducing bias and inefficiency in the selection algorithm. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application, pp. 14\u201321. Lawrence Erlbaum Associates, Mahwah (1987)"},{"issue":"1","key":"9391_CR6","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1162\/evco.1995.3.1.81","volume":"3","author":"H.-G. Beyer","year":"1995","unstructured":"Beyer, H.-G.: Toward a theory of evolution strategies: On the benefit of sex\u2014the (\u03bc\/\u03bc,\u03bb)-theory. Evol. Comput. 3(1), 81\u2013111 (1995)","journal-title":"Evol. Comput."},{"issue":"1","key":"9391_CR7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1023\/A:1015059928466","volume":"1","author":"H.-G. Beyer","year":"2002","unstructured":"Beyer, H.-G., Schwefel, H.-P.: Evolution strategies: a comprehensive introduction. Nat. Comput. 1(1), 3\u201352 (2002)","journal-title":"Nat. Comput."},{"key":"9391_CR8","volume-title":"A probabilistic Theory of Pattern Recognition","author":"L. Devroye","year":"1997","unstructured":"Devroye, L., Gy\u00f6rfi, L., Lugosi, G.: A probabilistic Theory of Pattern Recognition. Springer, Berlin (1997)"},{"key":"9391_CR9","doi-asserted-by":"crossref","unstructured":"Droste, S.: Not all linear functions are equally difficult for the compact genetic algorithm. In: Proc. of the Genetic and Evolutionary Computation COnference (GECCO 2005), pp. 679\u2013686 (2005)","DOI":"10.1145\/1068009.1068124"},{"issue":"2","key":"9391_CR10","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1162\/evco.1998.6.2.185","volume":"6","author":"S. Droste","year":"1998","unstructured":"Droste, S., Jansen, T., Wegener, I.: A rigorous complexity analysis of the (1+1) evolutionary algorithm for separable functions with boolean inputs. Evol. Comput. 6(2), 185\u2013196 (1998)","journal-title":"Evol. Comput."},{"issue":"4","key":"9391_CR11","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1162\/evco.2007.15.4.411","volume":"15","author":"S. Gelly","year":"2007","unstructured":"Gelly, S., Ruette, S., Teytaud, O.: Comparison-based algorithms are robust and randomized algorithms are anytime. Evol. Comput. J. 15(4), 411\u2013434 (2007). Special issue on bridging Theory and Practice","journal-title":"Evol. Comput. J."},{"key":"9391_CR12","first-page":"529","volume-title":"Handbook of Discrete and Computational Geometry","author":"D. Halperin","year":"2004","unstructured":"Halperin, D.: Arrangements. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 529\u2013562. CRC Press, Boca Raton (2004). Chap.\u00a024"},{"issue":"2","key":"9391_CR13","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1162\/106365601750190398","volume":"9","author":"N. Hansen","year":"2001","unstructured":"Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evol. Comput. 9(2), 159\u2013195 (2001)","journal-title":"Evol. Comput."},{"issue":"2","key":"9391_CR14","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1145\/321062.321069","volume":"8","author":"R. Hooke","year":"1961","unstructured":"Hooke, R., Jeeves, T.A.: \u201cDirect search\u201d solution of numerical and statistical problems. J. ACM 8(2), 212\u2013229 (1961)","journal-title":"J. ACM"},{"key":"9391_CR15","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1007\/3-540-45061-0_82","volume-title":"30th International Colloquium on Automata, Languages, and Programming (ICALP 2003)","author":"J. J\u00e4gersk\u00fcpper","year":"2003","unstructured":"J\u00e4gersk\u00fcpper, J.: Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces. In: 30th International Colloquium on Automata, Languages, and Programming (ICALP 2003). LNCS, vol. 2719, pp. 1068\u20131079. Springer, Berlin (2003)"},{"issue":"3","key":"9391_CR16","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/j.tcs.2007.02.042","volume":"379","author":"J. J\u00e4gersk\u00fcpper","year":"2007","unstructured":"J\u00e4gersk\u00fcpper, J.: Analysis of a simple evolutionary algorithm for minimization in Euclidean spaces. Theor. Comput. Sci. 379(3), 329\u2013347 (2007). Special issue on ICALP 2003","journal-title":"Theor. Comput. Sci."},{"key":"9391_CR17","doi-asserted-by":"crossref","unstructured":"J\u00e4gersk\u00fcpper, J., Witt, C.: Rigorous runtime analysis of a (\u03bc+1)-ES for the sphere function. In: GECCO, pp. 849\u2013856 (2005)","DOI":"10.1145\/1068009.1068153"},{"key":"9391_CR18","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol.\u00a0212. Springer, Berlin (2002)"},{"key":"9391_CR19","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/1102256.1102330","volume-title":"GECCO\u201905: Proceedings of the 2005 Workshops on Genetic and Evolutionary Computation","author":"A. Moraglio","year":"2005","unstructured":"Moraglio, A., Poli, R.: Topological crossover for the permutation representation. In: GECCO\u201905: Proceedings of the 2005 Workshops on Genetic and Evolutionary Computation, pp. 332\u2013338. ACM, New York (2005)"},{"issue":"9","key":"9391_CR20","doi-asserted-by":"crossref","first-page":"2750","DOI":"10.1016\/j.cor.2006.12.009","volume":"35","author":"F. Neumann","year":"2008","unstructured":"Neumann, F.: Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. Computers & OR 35(9), 2750\u20132759 (2008)","journal-title":"Computers & OR"},{"key":"9391_CR21","volume-title":"Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution","author":"I. Rechenberg","year":"1973","unstructured":"Rechenberg, I.: Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien des Biologischen Evolution. Fromman-Holzboog Verlag, Stuttgart (1973)"},{"issue":"3","key":"9391_CR22","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1090\/S0894-0347-01-00367-8","volume":"14","author":"L. R\u00f3nyai","year":"2001","unstructured":"R\u00f3nyai, L., Babai, L., Ganapathy, M.K.: On the number of zero-patterns of a sequence of polynomials. J. Am. Math. Soc. 14(3), 717\u2013735 (2001)","journal-title":"J. Am. Math. Soc."},{"issue":"3","key":"9391_CR23","first-page":"375","volume":"26","author":"G. Rudolph","year":"1997","unstructured":"Rudolph, G.: Convergence rates of evolutionary algorithms for a class of convex objective functions. Control Cybern. 26(3), 375\u2013390 (1997)","journal-title":"Control Cybern."},{"issue":"1","key":"9391_CR24","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Comb. Theory, Ser. A 13(1), 145\u2013147 (1972)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9391_CR25","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/1389095.1389114","volume-title":"GECCO\u201908: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation","author":"D. Sudholt","year":"2008","unstructured":"Sudholt, D., Witt, C.: Runtime analysis of binary PSO. In: GECCO\u201908: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, pp. 135\u2013142. ACM, New York (2008)"},{"key":"9391_CR26","doi-asserted-by":"crossref","unstructured":"Teytaud, O., Gelly, S.: General lower bounds for evolutionary algorithms. In: Proceedings of PPSN, pp. 21\u201331 (2006)","DOI":"10.1007\/11844297_3"},{"key":"9391_CR27","doi-asserted-by":"crossref","unstructured":"Teytaud, O., Fournier, H.: Lower bounds for evolution strategies using vc-dimension. In: PPSN, pp. 102\u2013111 (2008)","DOI":"10.1007\/978-3-540-87700-4_11"},{"issue":"2","key":"9391_CR28","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"XVI","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Ya.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. XVI(2), 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."},{"key":"9391_CR29","first-page":"116","volume-title":"Proceedings of the Third International Conference on Genetic Algorithms","author":"D. Whitley","year":"1989","unstructured":"Whitley, D.: The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In: Schaffer, J.D. (ed.) Proceedings of the Third International Conference on Genetic Algorithms, pp. 116\u2013121. Morgan Kaufman, San Mateo (1989)"},{"key":"9391_CR30","doi-asserted-by":"crossref","first-page":"3551","DOI":"10.1145\/1570256.1570430","volume-title":"GECCO\u201909: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference","author":"C. Witt","year":"2009","unstructured":"Witt, C.: Theory of randomised search heuristics in combinatorial optimisation: an algorithmic point of view. In: GECCO\u201909: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, pp. 3551\u20133592. ACM, New York (2009)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9391-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9391-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9391-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:05Z","timestamp":1559137505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9391-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,23]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["9391"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9391-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,23]]}}}