{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:41:46Z","timestamp":1777596106744,"version":"3.51.4"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T00:00:00Z","timestamp":1346198400000},"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":[[2014,3]]},"DOI":"10.1007\/s00453-012-9684-9","type":"journal-article","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T19:35:31Z","timestamp":1346182531000},"page":"571-609","source":"Crossref","is-referenced-by-count":31,"title":["Ranking-Based Black-Box Complexity"],"prefix":"10.1007","volume":"68","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carola","family":"Winzen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,29]]},"reference":[{"key":"9684_CR1","first-page":"465","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC\u201904)","author":"S. Aaronson","year":"2004","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC\u201904), pp. 465\u2013474. ACM Press, New York (2004)"},{"key":"9684_CR2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1214\/aop\/1176993605","volume":"11","author":"D. Aldous","year":"1983","unstructured":"Aldous, D.: Minimization algorithms and random walk on the d-cube. Ann. Probab. 11, 403\u2013413 (1983)","journal-title":"Ann. Probab."},{"key":"9684_CR3","first-page":"67","volume-title":"Proceedings of Foundations of Genetic Algorithms (FOGA\u201909)","author":"G. Anil","year":"2009","unstructured":"Anil, G., Wiegand, R.P.: Black-box search by elimination of fitness functions. In: Proceedings of Foundations of Genetic Algorithms (FOGA\u201909), pp. 67\u201378. ACM Press, New York (2009)"},{"key":"9684_CR4","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF02579188","volume":"3","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Mastermind. Combinatorica 3, 325\u2013329 (1983)","journal-title":"Combinatorica"},{"key":"9684_CR5","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1145\/1967654.1967669","volume-title":"Proceedings of Foundations of Genetic Algorithms (FOGA\u201911)","author":"B. Doerr","year":"2011","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 Press, New York (2011)"},{"key":"9684_CR6","doi-asserted-by":"crossref","first-page":"2043","DOI":"10.1145\/2001576.2001851","volume-title":"Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO\u201911)","author":"B. Doerr","year":"2011","unstructured":"Doerr, B., K\u00f6tzing, T., Winzen, C.: Too fast unbiased black-box algorithms. In: Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO\u201911), pp. 2043\u20132050. ACM Press, New York (2011)"},{"key":"9684_CR7","first-page":"15","volume-title":"Proceedings of Computer Science Symposium in Russia (CSR\u201911)","author":"B. Doerr","year":"2011","unstructured":"Doerr, B., Winzen, C.: Towards a complexity theory of randomized search heuristics: ranking-based black-box complexity. In: Proceedings of Computer Science Symposium in Russia (CSR\u201911), pp.\u00a015\u201328. Springer, Berlin (2011)"},{"key":"9684_CR8","first-page":"253","volume-title":"Proceedings of Foundations of Genetic Algorithms (FOGA\u201903)","author":"S. Droste","year":"2003","unstructured":"Droste, S., Jansen, T., Tinnefeld, K., Wegener, I.: A new framework for the valuation of algorithms for black-box optimization. In: Proceedings of Foundations of Genetic Algorithms (FOGA\u201903), pp. 253\u2013270. Morgan Kaufmann, San Mateo (2003)"},{"key":"9684_CR9","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) evolutionary algorithm. Theor. Comput. Sci. 276, 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9684_CR10","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":"9684_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D. Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"9684_CR12","first-page":"229","volume":"8","author":"P. Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On two problems of information theory. Magy. Tud. Akad. Mat. Kut. Int\u00e9z. K\u00f6zl. 8, 229\u2013243 (1963)","journal-title":"Magy. Tud. Akad. Mat. Kut. Int\u00e9z. K\u00f6zl."},{"key":"9684_CR13","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s00453-010-9391-3","volume":"59","author":"H. Fournier","year":"2011","unstructured":"Fournier, H., Teytaud, O.: Lower bounds for comparison based evolution strategies using vc-dimension and sign patterns. Algorithmica 59, 387\u2013408 (2011)","journal-title":"Algorithmica"},{"key":"9684_CR14","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1990)"},{"key":"9684_CR15","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1016\/j.ipl.2009.02.021","volume":"109","author":"M.T. Goodrich","year":"2009","unstructured":"Goodrich, M.T.: On the algorithmic complexity of the mastermind game with black-peg results. Inf. Process. Lett. 109, 675\u2013678 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9684_CR16","volume-title":"Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics","author":"J. Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Berlin (2003)"},{"key":"9684_CR17","doi-asserted-by":"crossref","first-page":"1441","DOI":"10.1145\/1830483.1830747","volume-title":"Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201910)","author":"P.K. Lehre","year":"2010","unstructured":"Lehre, P.K., Witt, C.: Black-box search by unbiased variation. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO\u201910), pp. 1441\u20131448. ACM Press, New York (2010). A\u00a0journal version of this paper is to appear in Algorithmica. doi: 10.1007\/s00453-012-9616-8"},{"key":"9684_CR18","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0166-218X(89)90025-5","volume":"23","author":"D.C. Llewellyn","year":"1989","unstructured":"Llewellyn, D.C., Tovey, C., Trick, M.: Local optimization on graphs. Discrete Appl. Math. 23, 157\u2013178 (1989). Erratum 46, 93\u201394, 1993","journal-title":"Discrete Appl. Math."},{"key":"9684_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07807-5","volume-title":"How to Solve It\u2014Modern Heuristics","author":"Z. Michalewicz","year":"2004","unstructured":"Michalewicz, Z., Fogel, D.B.: How to Solve It\u2014Modern Heuristics, 2nd edn. Springer, Berlin (2004)","edition":"2"},{"key":"9684_CR20","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":"9684_CR21","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 378, 32\u201340 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9684_CR22","doi-asserted-by":"crossref","first-page":"26","DOI":"10.2307\/2308012","volume":"62","author":"H. Robbins","year":"1955","unstructured":"Robbins, H.: A remark on Stirling\u2019s formula. Am. Math. Mon. 62, 26\u201329 (1955)","journal-title":"Am. Math. Mon."},{"key":"9684_CR23","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/11844297_3","volume-title":"Proceedings of the 9th International Conference on Parallel Problem Solving from Nature\u2014PPSN IX (PPSN\u201906)","author":"O. Teytaud","year":"2006","unstructured":"Teytaud, O., Gelly, S.: General lower bounds for evolutionary algorithms. In: Proceedings of the 9th International Conference on Parallel Problem Solving from Nature\u2014PPSN IX (PPSN\u201906), pp. 21\u201331. Springer, Berlin (2006)"},{"key":"9684_CR24","first-page":"222","volume-title":"Proceedings of 18th Annual Symposium on Foundations of Computer Science (FOCS\u201977)","author":"A.C.-C. Yao","year":"1977","unstructured":"Yao, A.C.-C.: Probabilistic computations: toward a unified measure of complexity. In: Proceedings of 18th Annual Symposium on Foundations of Computer Science (FOCS\u201977), pp. 222\u2013227 (1977)"},{"key":"9684_CR25","first-page":"634","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906)","author":"S. Zhang","year":"2006","unstructured":"Zhang, S.: New upper and lower bounds for randomized and quantum local search. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906), pp. 634\u2013643. ACM Press, New York (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9684-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9684-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9684-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T19:35:09Z","timestamp":1643312109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9684-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,29]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9684"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9684-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,29]]}}}