{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:39:20Z","timestamp":1761896360133,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T00:00:00Z","timestamp":1472428800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T00:00:00Z","timestamp":1472428800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP140103400"],"award-info":[{"award-number":["DP140103400"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["618091"],"award-info":[{"award-number":["618091"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00453-016-0190-3","type":"journal-article","created":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T13:54:24Z","timestamp":1472478864000},"page":"561-586","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas"],"prefix":"10.1007","volume":"78","author":[{"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew M.","family":"Sutton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,29]]},"reference":[{"key":"190_CR1","unstructured":"Achlioptas, D.: Random satisfiability. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 245\u2013270. IOS Press, Amsterdam, Netherlands (2009)"},{"issue":"3","key":"190_CR2","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1002\/rsa.20323","volume":"38","author":"D Achlioptas","year":"2011","unstructured":"Achlioptas, D., Coja-Oghlan, A., Ricci-Tersenghi, F.: On the solution-space geometry of random constraint satisfaction problems. Random Struct. Algorithms 38(3), 251\u2013268 (2011)","journal-title":"Random Struct. Algorithms"},{"issue":"5","key":"190_CR3","doi-asserted-by":"publisher","first-page":"1248","DOI":"10.1137\/S0097539704440107","volume":"36","author":"M Alekhnovich","year":"2007","unstructured":"Alekhnovich, M., Ben-Sasson, E.: Linear upper bounds for random walk on small density random 3-CNFs. SIAM J. Comput. 36(5), 1248\u20131263 (2007)","journal-title":"SIAM J. Comput."},{"key":"190_CR4","unstructured":"Altenberg, L.: Fitness distance correlation analysis: an instructive counterexample. In: B\u00e4ck, T. (eds.) Proceedings of the Seventh International Conference on Genetic Algorithms, pp. 57\u201364. Morgan Kaufmann (1997)"},{"volume-title":"Theory of Randomized Search Heuristics: Foundations and Recent Developments","year":"2011","key":"190_CR5","unstructured":"Auger, A., Doerr, B. (eds.): Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Co. Inc., Singapore (2011)"},{"key":"190_CR6","unstructured":"Ben-Sasson, E., Bilu, Y., Gutfreund, D.: Finding a randomly planted assignment in a random 3-CNF (2002, unpublished manuscript)"},{"key":"190_CR7","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., Skvortsov, E.S.: Phase transition for local search on planted SAT. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) Mathematical Foundations of Computer Science 2015, volume 9235 of Lecture Notes in Computer Science, vol. 9235, pp.175\u2013186. Springer Berlin, Heidelberg (2015)","DOI":"10.1007\/978-3-662-48054-0_15"},{"key":"190_CR8","doi-asserted-by":"crossref","unstructured":"Clark, D.A., Frank, J., Gent, I.P., MacIntyre, E., Tomov, N., Walsh, T.: Local search and the number of solutions. In: Freuder, E.C. (ed.) Proceedings of the Second International Conference on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, vol. 1118, pp. 119\u2013133. Springer, Berlin Heidelberg (1996)","DOI":"10.1007\/3-540-61551-2_70"},{"issue":"4","key":"190_CR9","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1137\/12090191X","volume":"43","author":"A Coja-Oghlan","year":"2014","unstructured":"Coja-Oghlan, A., Frieze, A.: Analyzing walksat on random formulas. SIAM J. Comput. 43(4), 1456\u20131485 (2014)","journal-title":"SIAM J. Comput."},{"key":"190_CR10","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1016\/j.aim.2015.11.007","volume":"288","author":"A Coja-Oghlan","year":"2016","unstructured":"Coja-Oghlan, A., Panagiotou, K.: The asymptotic $$k$$-SAT threshold. Adv. Math. 288, 985\u20131068 (2016)","journal-title":"Adv. Math."},{"issue":"1\u20132","key":"190_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0004-3702(95)00046-1","volume":"81","author":"JM Crawford","year":"1996","unstructured":"Crawford, J.M., Auton, L.D.: Experimental results on the crossover point in random 3-SAT. Artif. Intell. 81(1\u20132), 31\u201357 (1996)","journal-title":"Artif. Intell."},{"key":"190_CR12","doi-asserted-by":"crossref","unstructured":"Ding, J., Sly, A., Sun, N.: Proof of the satisfiability conjecture for large $$k$$. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pp. 59\u201368, ACM, New York, NY, USA (2015)","DOI":"10.1145\/2746539.2746619"},{"key":"190_CR13","doi-asserted-by":"crossref","unstructured":"Doerr, B.: Analyzing randomized search heuristics: tools from probability theory. In: Auger and Doerr [5], pp. 1\u201320","DOI":"10.1142\/9789814282673_0001"},{"issue":"1","key":"190_CR14","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","volume":"65","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Ann Goldberg, L.: Adaptive drift analysis. Algorithmica 65(1), 224\u2013250 (2013)","journal-title":"Algorithmica"},{"issue":"4","key":"190_CR15","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64(4), 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"190_CR16","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F., Sutton, A.M.: Improved runtime bounds for the ($$1+1$$) EA on random 3-CNF formulas based on fitness-distance correlation. In: Laredo, J.L.J., Silva, S., Esparcia-Alc\u00e1zar, A.I. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2015), pp. 1415\u20131422. ACM (2015)","DOI":"10.1145\/2739480.2754659"},{"key":"190_CR17","doi-asserted-by":"crossref","unstructured":"Doerr, B., Sudholt, D., Witt, C.: When do evolutionary algorithms optimize separable functions in parallel? In: Proceedings of the Twelfth ACM SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA 2013), pp. 48\u201359. ACM (2013)","DOI":"10.1145\/2460239.2460245"},{"issue":"1\u20132","key":"190_CR18","doi-asserted-by":"publisher","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(1\u20132), 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"190_CR19","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/s00453-013-9801-4","volume":"68","author":"M Englert","year":"2014","unstructured":"Englert, M., R\u00f6glin, H., V\u00f6cking, B.: Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica 68(1), 190\u2013264 (2014)","journal-title":"Algorithmica"},{"issue":"4","key":"190_CR20","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1002\/rsa.20213","volume":"32","author":"AD Flaxman","year":"2008","unstructured":"Flaxman, A.D.: A spectral technique for random satisfiable 3CNF formulas. Random Struct. Algorithms 32(4), 519\u2013534 (2008)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"190_CR21","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"A Frieze","year":"1996","unstructured":"Frieze, A., Suen, S.: Analysis of two simple heuristics on a random instance of $$k$$-SAT. J. Algorithms 20(2), 312\u2013355 (1996)","journal-title":"J. Algorithms"},{"key":"190_CR22","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-662-04448-3_18","volume-title":"Theoretical Aspects of Evolutionary Computing, Natural Computing Series","author":"T Jansen","year":"2001","unstructured":"Jansen, T.: On classifications of fitness functions. In: Kallel, L., Naudts, B., Rogers, A. (eds.) Theoretical Aspects of Evolutionary Computing, Natural Computing Series, pp. 371\u2013385. Springer, Berlin (2001)"},{"key":"190_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective","author":"T Jansen","year":"2013","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms\u2014The Computer Science Perspective. Springer, Berlin (2013). (Natural Computing Series)"},{"key":"190_CR24","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.tcs.2013.06.007","volume":"545","author":"T Jansen","year":"2014","unstructured":"Jansen, T., Zarges, C.: Performance analysis of randomised search heuristics operating with a fixed budget. Theor. Comput. Sci. 545, 39\u201358 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"190_CR25","unstructured":"Jones, T., Forrest, S.: Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In: Eshelman, L.J. (eds.) Proceedings of the Sixth International Conference on Genetic Algorithms, pp. 184\u2013192. Morgan Kaufmann (1995)"},{"issue":"5163","key":"190_CR26","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","volume":"264","author":"S Kirkpatrick","year":"1994","unstructured":"Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random Boolean expressions. Science 264(5163), 1297\u20131301 (1994)","journal-title":"Science"},{"issue":"1","key":"190_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11721-011-0059-7","volume":"6","author":"T K\u00f6tzing","year":"2012","unstructured":"K\u00f6tzing, T., Neumann, F., R\u00f6glin, H., Witt, C.: Theoretical analysis of two ACO approaches for the traveling salesman problem. Swarm Intell 6(1), 1\u201321 (2012)","journal-title":"Swarm Intell"},{"issue":"1","key":"190_CR28","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(92)90029-U","volume":"43","author":"E Koutsoupias","year":"1992","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the greedy algorithm for satisfiability. Inf. Process. Lett. 43(1), 53\u201355 (1992)","journal-title":"Inf. Process. Lett."},{"key":"190_CR29","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Vilenchik, D.: Solving random satisfiable 3CNF formulas in expected polynomial time. In: Proceedings of the Seventeenth Symposium on Discrete Algorithms (SODA 2006), pp. 454\u2013463 (2006)","DOI":"10.1145\/1109557.1109608"},{"issue":"3","key":"190_CR30","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","volume":"51","author":"C Ming-Te","year":"1990","unstructured":"Ming-Te, C., Franco, J.: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the $$k$$ satisfiability problem. Inf. Sci. 51(3), 289\u2013314 (1990)","journal-title":"Inf. Sci."},{"key":"190_CR31","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of SAT problems. In: Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI 1992), pp. 459\u2013465 (1992)"},{"key":"190_CR32","unstructured":"Mitzenmacher, M.: Tight thresholds for the pure literal rule. (1997). Technical Report 1997-011, Digital SRC"},{"issue":"1","key":"190_CR33","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/rsa.20061","volume":"27","author":"M Molloy","year":"2005","unstructured":"Molloy, M.: Cores in random hypergraphs and Boolean formulas. Random Struct. Algorithms 27(1), 124\u2013135 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"190_CR34","doi-asserted-by":"crossref","unstructured":"Nallaperuma, S., Neumann, F., Sudholt, D.: A fixed budget analysis of randomized search heuristics for the traveling salesperson problem. In: Arnold, D.V. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2014), pp. 807\u2013814. ACM (2014)","DOI":"10.1145\/2576768.2598302"},{"key":"190_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3","volume-title":"Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity","author":"F Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer, Berlin (2010)"},{"key":"190_CR36","unstructured":"Papadimitriou, C.H.: On selecting a satisfying truth assignment. In: Proceedings of 32nd Annual Symposium on Foundations of Computer Science, 1991, pp. 163\u2013169. (1991)"},{"key":"190_CR37","doi-asserted-by":"crossref","unstructured":"Quick, R.J., Rayward-Smith, V.J., Smith, G.D.: Fitness distance correlation and ridge functions. In Eiben, A.E., B\u00e4ck, T., Schoenauer, M., Schwefel, H-P. (eds.) Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature (PPSN V), volume 1498 of Lecture Notes in Computer Science, vol. 1498, pp.77\u201386. Springer (1998)","DOI":"10.1007\/BFb0056851"},{"issue":"1","key":"190_CR38","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02579445","volume":"5","author":"J Schmidt-Pruzan","year":"1985","unstructured":"Schmidt-Pruzan, J., Shamir, E.: Component structure in the evolution of random hypergraphs. Combinatorica 5(1), 81\u201394 (1985)","journal-title":"Combinatorica"},{"key":"190_CR39","doi-asserted-by":"crossref","unstructured":"Skvortsov, E.S.: A theoretical analysis of search in GSAT. In: Kullmann, O. (ed.) Theory and Applications of Satisfiability Testing (SAT 2009), volume 5584 of Lecture Notes in Computer Science, vol. 5584, pp. 265\u2013275. Springer Berlin, Heidelberg (2009)","DOI":"10.1007\/978-3-642-02777-2_26"},{"key":"190_CR40","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.tcs.2007.06.008","volume":"386","author":"T Storch","year":"2007","unstructured":"Storch, T.: Finding large cliques in sparse semi-random graphs by simple randomized search heuristics. Theor. Comput. Sci. 386, 114\u2013131 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"190_CR41","doi-asserted-by":"crossref","unstructured":"Sutton A.M., Neumann, F.: Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas. In: Bartz-Beielstein, T., Branke, J., Filipic, B., Smith, J. (eds.) Proceedings of the Thirteenth International Conference on Parallel Problem Solving from Nature (PPSN XIII), volume 8672 of Lecture Notes in Computer Science, vol. 8672, pp. 942\u2013951. Springer (2014)","DOI":"10.1007\/978-3-319-10762-2_93"},{"key":"190_CR42","doi-asserted-by":"crossref","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In Diekert, V., Durand, B. (eds.) STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings, volume 3404 of Lecture Notes in Computer Science, vol. 3404, pp. 44\u201356. Springer (2005)","DOI":"10.1007\/978-3-540-31856-9_4"},{"issue":"1\u20132","key":"190_CR43","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.ipl.2013.09.013","volume":"114","author":"C Witt","year":"2014","unstructured":"Witt, C.: Fitness levels with tail bounds for the analysis of randomized search heuristics. Inf. Process. Lett. 114(1\u20132), 38\u201341 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"9","key":"190_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11432-012-4653-0","volume":"56","author":"YR Zhou","year":"2013","unstructured":"Zhou, Y.R.: Exponential bounds for the random walk algorithm on random planted 3-sat. Sci. China Inf. Sci. 56(9), 1\u201313 (2013)","journal-title":"Sci. China Inf. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0190-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0190-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0190-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0190-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T06:57:40Z","timestamp":1657177060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0190-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,29]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["190"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0190-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,8,29]]},"assertion":[{"value":"12 October 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}