{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:04:49Z","timestamp":1773655489579,"version":"3.50.1"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319107615","type":"print"},{"value":"9783319107622","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-10762-2_93","type":"book-chapter","created":{"date-parts":[[2014,9,10]],"date-time":"2014-09-10T14:58:55Z","timestamp":1410361135000},"page":"942-951","source":"Crossref","is-referenced-by-count":6,"title":["Runtime Analysis of Evolutionary Algorithms on Randomly Constructed High-Density Satisfiable 3-CNF Formulas"],"prefix":"10.1007","author":[{"given":"Andrew M.","family":"Sutton","sequence":"first","affiliation":[]},{"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"93_CR1","doi-asserted-by":"crossref","unstructured":"Auger, A., Doerr, B.: Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Company (2011)","DOI":"10.1142\/7438"},{"key":"93_CR2","unstructured":"Ben-Sasson, E., Bilu, Y., Gutfreund, D.: Finding a randomly planted assignment in a random 3-CNF (2002) (manuscript)"},{"key":"93_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-642-15844-5_18","volume-title":"Parallel Problem Solving from Nature, PPSN XI","author":"B. Doerr","year":"2010","unstructured":"Doerr, B., Goldberg, L.A.: Drift analysis with tail bounds. In: Schaefer, R., Cotta, C., Ko\u0142odziej, J., Rudolph, G. (eds.) PPSN XI. LNCS, vol.\u00a06238, pp. 174\u2013183. Springer, Heidelberg (2010)"},{"issue":"4","key":"93_CR4","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\u00a064(4), 673\u2013697 (2012)","journal-title":"Algorithmica"},{"issue":"1-2","key":"93_CR5","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. Theoretical Computer Science\u00a0276(1-2), 51\u201381 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"93_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1162\/106365602317301763","volume":"10","author":"J. Gottlieb","year":"2002","unstructured":"Gottlieb, J., Marchiori, E., Rossi, C.: Evolutionary algorithms for the satisfiability problem. Evolutionary Computation\u00a010(1), 35\u201350 (2002)","journal-title":"Evolutionary Computation"},{"issue":"1","key":"93_CR7","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. Information Processing Letters\u00a043(1), 53\u201355 (1992)","journal-title":"Information Processing Letters"},{"key":"93_CR8","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1017\/S0963548309990356","volume":"18","author":"M. Krivelevich","year":"2009","unstructured":"Krivelevich, M., Sudakov, B., Vilenchik, D.: On the random satisfiability process. Combinatorics, Probability and Computing\u00a018, 775\u2013801 (2009)","journal-title":"Combinatorics, Probability and Computing"},{"key":"93_CR9","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Vilenchik, D.: Solving random satisfiable 3CNF formulas in expected polynomial time. In: SODA, pp. 454\u2013463 (2006)","DOI":"10.1145\/1109557.1109608"},{"key":"93_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/978-3-642-14186-7_31","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2010","author":"L. Kroc","year":"2010","unstructured":"Kroc, L., Sabharwal, A., Selman, B.: An empirical study of optimal noise and runtime distributions in local search. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol.\u00a06175, pp. 346\u2013351. Springer, Heidelberg (2010)"},{"key":"93_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, New York (1995)"},{"key":"93_CR12","doi-asserted-by":"crossref","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization \u2013 Algorithms and Their Computational Complexity. Springer (2010)","DOI":"10.1007\/978-3-642-16544-3"},{"key":"93_CR13","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S1571-0653(04)00463-9","volume":"16","author":"S. Seitz","year":"2003","unstructured":"Seitz, S., Orponen, P.: An efficient local search method for random 3-satisfiability. Electronic Notes in Discrete Mathematics\u00a016, 71\u201379 (2003)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"93_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/978-3-642-03751-1_4","volume-title":"Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics","author":"A.M. Sutton","year":"2009","unstructured":"Sutton, A.M., Howe, A.E., Whitley, L.D.: A theoretical analysis of the k-satisfiability search space. In: St\u00fctzle, T., Birattari, M., Hoos, H.H. (eds.) SLS 2009. LNCS, vol.\u00a05752, pp. 46\u201360. Springer, Heidelberg (2009)"},{"key":"93_CR15","doi-asserted-by":"crossref","unstructured":"Sutton, A.M., Whitley, L.D., Howe, A.E.: A polynomial time computation of the exact correlation structure of k-satisfiability landscapes. In: GECCO (2009)","DOI":"10.1145\/1569901.1569952"},{"key":"93_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-540-31856-9_4","volume-title":"STACS 2005","author":"C. Witt","year":"2005","unstructured":"Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 44\u201356. Springer, Heidelberg (2005)"},{"issue":"2","key":"93_CR17","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1017\/S0963548312000600","volume":"22","author":"C. Witt","year":"2013","unstructured":"Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combinatorics, Probability and Computing\u00a022(2), 294\u2013318 (2013)","journal-title":"Combinatorics, Probability and Computing"}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XIII"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-10762-2_93","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T21:30:03Z","timestamp":1565818203000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-10762-2_93"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319107615","9783319107622"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-10762-2_93","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}