{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T20:15:33Z","timestamp":1760645733239},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,4,13]],"date-time":"2010-04-13T00:00:00Z","timestamp":1271116800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2010,6]]},"DOI":"10.1007\/s11786-010-0040-7","type":"journal-article","created":{"date-parts":[[2010,4,12]],"date-time":"2010-04-12T17:10:14Z","timestamp":1271092214000},"page":"465-488","source":"Crossref","is-referenced-by-count":9,"title":["Analysis of Local Search Landscapes for k-SAT Instances"],"prefix":"10.1007","volume":"3","author":[{"given":"A. A.","family":"Albrecht","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P. C. R.","family":"Lane","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Steinh\u00f6fel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,4,13]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1090\/S0894-0347-04-00464-3","volume":"17","author":"D. Achlioptas","year":"2004","unstructured":"Achlioptas D., Peres Y.: . J. Am. Math. Soc. 17, 947\u2013973 (2004)","journal-title":"J. Am. Math. Soc."},{"key":"40_CR2","doi-asserted-by":"crossref","first-page":"15253","DOI":"10.1073\/pnas.0712263105","volume":"105","author":"M. Alava","year":"2008","unstructured":"Alava M., Ardelius J., Aurell E., Kaski P., Krishnamurthy S., Orponen P., Seitz S.: Circumspect descent prevails in solving random constraint satisfaction problems. PNAS USA 105, 15253\u201315257 (2008)","journal-title":"PNAS USA"},{"key":"40_CR3","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s00607-006-0167-1","volume":"78","author":"A.A. Albrecht","year":"2006","unstructured":"Albrecht A.A.: A stopping criterion for logarithmic simulated annealing. Computing 78, 55\u201379 (2006)","journal-title":"Computing"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Albrecht, A.A., Lane, P.C.R., Steinh\u00f6fel, K.: Combinatorial landscape analysis for k-SAT instances. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 2498\u20132504 (2008)","DOI":"10.1109\/CEC.2008.4631133"},{"key":"40_CR5","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1016\/j.compbiolchem.2008.03.004","volume":"32","author":"A.A. Albrecht","year":"2008","unstructured":"Albrecht A.A., Skaliotis A., Steinh\u00f6fel K.: Stochastic protein folding simulation in the d-dimensional HP-model. Comput. Biol. Chem. 32, 248\u2013255 (2008)","journal-title":"Comput. Biol. Chem."},{"key":"40_CR6","unstructured":"Barvinok, A.: On the number of matrices and a random matrix with prescribed row and column sums and 0\u20131 entries. arXiv:0806.1480v2 (2008)"},{"key":"40_CR7","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.tcs.2004.08.002","volume":"329","author":"T. Brueggemann","year":"2004","unstructured":"Brueggemann T., Kern W.: An improved local search algorithm for 3-SAT. Theor. Comput. Sci. 329, 303\u2013313 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"40_CR8","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.jcta.2007.03.009","volume":"115","author":"E.R. Canfield","year":"2008","unstructured":"Canfield E.R., Greenhill C., McKay B.D.: Asymptotic enumeration of dense 0\u20131 matrices with specified line sums. J. Comb. Theory (Series A) 115, 32\u201366 (2008)","journal-title":"J. Comb. Theory (Series A)"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Dantsin, E., Wolpert, A.: An improved upper bound for SAT. In: Proceedings of SAT 2005, LNCS, vol. 3569, pp. 400\u2013407 (2005)","DOI":"10.1007\/11499107_31"},{"key":"40_CR10","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1137\/S0895480199355225","volume":"15","author":"J. Garnier","year":"2002","unstructured":"Garnier J., Kallel L.: Efficiency of local search with multiple local optima. SIAM J. Discrete Math. 15, 122\u2013141 (2002)","journal-title":"SIAM J. Discrete Math."},{"key":"40_CR11","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1023\/A:1025846120461","volume":"8","author":"A. Gerevini","year":"2003","unstructured":"Gerevini A., Serina I.: Planning as propositional CSP: From WalkSAT to local search techniques for action graphs. Constraints 8, 389\u2013413 (2003)","journal-title":"Constraints"},{"key":"40_CR12","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1287\/ijoc.1040.0073","volume":"16","author":"H.J. Greenberg","year":"2004","unstructured":"Greenberg H.J., Hart W.E., Lancia G.: Opportunities for combinatorial optimization in computational biology. INFORMS J. Comput. 16, 211\u2013231 (2004)","journal-title":"INFORMS J. Comput."},{"key":"40_CR13","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1990","unstructured":"Hagerup T., R\u00fcb C.: A guided tour of Chernoff bounds. Inf. Process. Lett. 33, 305\u2013308 (1990)","journal-title":"Inf. Process. Lett."},{"key":"40_CR14","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0004-3702(99)00048-X","volume":"112","author":"H.H. Hoos","year":"1999","unstructured":"Hoos H.H., St\u00fctzle T.: Towards a characterisation of the behaviour of stochastic local search algorithms for SAT. Artif. Intell. 112, 213\u2013232 (1999)","journal-title":"Artif. Intell."},{"key":"40_CR15","unstructured":"Kaski, P.: Barriers and local minima in energy landscapes of stochastic local search. arXiv:cs\/0611103v1 (2006)"},{"key":"40_CR16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(01)00149-9","volume":"265","author":"O.C. Martin","year":"2001","unstructured":"Martin O.C., Monasson R., Zecchina R.: Statistical mechanics methods and phase transitions in optimization problems. Theor. Comput. Sci. 265, 3\u201367 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"40_CR17","doi-asserted-by":"crossref","first-page":"056126-1","DOI":"10.1103\/PhysRevE.66.056126","volume":"66","author":"M. M\u00e9zard","year":"2002","unstructured":"M\u00e9zard M., Zecchina R.: Random K-satisfiability problem: from an analytic solution to an efficient algorithm. Phys. Rev. E 66, 056126-1\u2013056126-27 (2002)","journal-title":"Phys. Rev. E"},{"key":"40_CR18","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of SAT problems. In: Proceedings of 10th National Conference on Artificial Intelligence, pp. 459\u2013465 (1992)"},{"key":"40_CR19","doi-asserted-by":"crossref","first-page":"1357","DOI":"10.1103\/PhysRevE.56.1357","volume":"56","author":"R. Monasson","year":"1997","unstructured":"Monasson R., Zecchina R.: Statistical mechanics of the random K-SAT problem. Phys. Rev. E 56, 1357\u20131361 (1997)","journal-title":"Phys. Rev. E"},{"key":"40_CR20","doi-asserted-by":"crossref","first-page":"2073","DOI":"10.1088\/0305-4470\/37\/6\/008","volume":"37","author":"A. Montanari","year":"2004","unstructured":"Montanari A., Parisi G., Ricci-Tersenghi F.: Instability of one-step replica-symmetry-broken phase in satisfiability problems. J. Phys. A: Math. Gen. 37, 2073\u20132091 (2004)","journal-title":"J. Phys. A: Math. Gen."},{"key":"40_CR21","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R. Paturi","year":"2005","unstructured":"Paturi R., Pudl\u00e1k P., Saks M.E., Zane F.: An improved exponential-time algorithm for k-SAT. J. ACM 52, 337\u2013364 (2005)","journal-title":"J. ACM"},{"key":"40_CR22","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1057\/palgrave.jors.2601611","volume":"55","author":"C.R. Reeves","year":"2004","unstructured":"Reeves C.R., Eremeev A.V.: Statistical analysis of local search landscapes. J. Oper. Res. Soc. 55, 687\u2013693 (2004)","journal-title":"J. Oper. Res. Soc."},{"key":"40_CR23","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1137\/S0036144501395952","volume":"44","author":"C.M. Reidys","year":"2002","unstructured":"Reidys C.M., Stadler P.F.: Combinatorial landscapes. SIAM Rev. 44, 3\u201354 (2002)","journal-title":"SIAM Rev."},{"key":"40_CR24","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":"40_CR25","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s00453-001-0094-7","volume":"32","author":"U. Sch\u00f6ning","year":"2002","unstructured":"Sch\u00f6ning U.: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica 32, 615\u2013623 (2002)","journal-title":"Algorithmica"},{"key":"40_CR26","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.jalgor.2004.04.012","volume":"54","author":"P. Schuler","year":"2005","unstructured":"Schuler P.: An algorithm for the satisfiability problem of formulas in conjunctive normal form. J. Algorithms 54, 40\u201344 (2005)","journal-title":"J. Algorithms"},{"key":"40_CR27","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0004-3702(01)00151-5","volume":"132","author":"D. Schuurmans","year":"2001","unstructured":"Schuurmans D., Southey F.: Local search characteristics of incomplete SAT procedures. Artif. Intell. 132, 121\u2013150 (2001)","journal-title":"Artif. Intell."},{"key":"40_CR28","doi-asserted-by":"crossref","unstructured":"Seitz, S., Alava, M., Orponen, P.: Threshold behaviour of WalkSAT and focused Metropolis search on random 3-satisfiability. In: Proceedings of SAT 2005, LNCS, vol. 3569, pp. 475\u2013481 (2005)","DOI":"10.1007\/11499107_41"},{"key":"40_CR29","doi-asserted-by":"crossref","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. Electron. Notes Discrete Math. 16, 71\u201379 (2003)","journal-title":"Electron. Notes Discrete Math."},{"key":"40_CR30","unstructured":"Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of AAAI, pp. 337\u2013343. MIT Press, Cambridge (1994)"},{"key":"40_CR31","unstructured":"Selman, B., Levesque, H., Mitchell, D.: A new method for solving hard satisfiability problems. In: Proceedings of AAAI, pp. 440\u2013446 (1992)"},{"key":"40_CR32","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.cpc.2006.12.002","volume":"176","author":"K. Steinh\u00f6fel","year":"2007","unstructured":"Steinh\u00f6fel K., Skaliotis A., Albrecht A.A.: Relating time complexity of protein folding simulation to approximations of folding time. Comput. Phys. Commun. 176, 165\u2013170 (2007)","journal-title":"Comput. Phys. Commun."},{"key":"40_CR33","volume-title":"Energy Landscapes","author":"D. Wales","year":"2003","unstructured":"Wales D.: Energy Landscapes. Cambridge University Press, Cambridge (2003)"},{"key":"40_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2004.04.001","volume":"158","author":"W. Zhang","year":"2004","unstructured":"Zhang W.: Configuration landscape analysis and backbone guided local search. Part I: satisfiability and maximum satisfiability. Artif. Intell. 158, 1\u201326 (2004)","journal-title":"Artif. Intell."}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-010-0040-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-010-0040-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-010-0040-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T18:32:28Z","timestamp":1559413948000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-010-0040-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,13]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["40"],"URL":"https:\/\/doi.org\/10.1007\/s11786-010-0040-7","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,4,13]]}}}