{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T05:49:27Z","timestamp":1744868967060},"reference-count":84,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,8,1]],"date-time":"2001-08-01T00:00:00Z","timestamp":996624000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4368,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,8]]},"DOI":"10.1016\/s0304-3975(01)00149-9","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T21:15:02Z","timestamp":1027631702000},"page":"3-67","source":"Crossref","is-referenced-by-count":121,"title":["Statistical mechanics methods and phase transitions in optimization problems"],"prefix":"10.1016","volume":"265","author":[{"given":"Olivier C.","family":"Martin","sequence":"first","affiliation":[]},{"given":"R\u00e9mi","family":"Monasson","sequence":"additional","affiliation":[]},{"given":"Riccardo","family":"Zecchina","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00149-9_BIB1","unstructured":"D.J. Aldous, The zeta(2) limit in the random assignment problem, Math.PR\/0010063."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB2","doi-asserted-by":"crossref","unstructured":"D. Applegate, R. Bixby, V. Chvtal, W. Cook, On the solution of traveling salesman problems, Documenta Math., J.D.M. ICM III 1998 (645\u2013656).","DOI":"10.4171\/dms\/1-3\/62"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB3","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/290179.290180","article-title":"Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems","volume":"45","author":"Arora","year":"1998","journal-title":"ACM"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB4","first-page":"L1","article-title":"Graph bipartitioning and statistical mechanics","volume":"20","author":"Banavar","year":"1987","journal-title":"J. Phys. A Lett."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB5","series-title":"Exactly solved models in Statistical Mechanics","author":"Baxter","year":"1982"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB6","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S0305004100034095","article-title":"The shortest path through many points","volume":"55","author":"Beardwood","year":"1959","journal-title":"Proc. Camb. Phil. Soc."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB7","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/s100510051065","article-title":"A variational description of the ground-state structure in random satisfiability problems","volume":"14","author":"Biroli","year":"2000","journal-title":"Eur. Phys. J. B"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(95)00184-0","article-title":"Length of prime implicants and number of solutions of random cnf formulas","volume":"215","author":"Boufkhad","year":"1999","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB9","unstructured":"A. Broder, A. Frieze, E. Upfal, On the satisfiability and maximum satisfiability of random 3-cnf formulas, Proc. 4th Annual ACM-SIAM Symp. on Discrete Algorithms, 1993, p. 322."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB10","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1209\/0295-5075\/14\/4\/002","article-title":"Extensive numerical simulations of weighted matchings","volume":"14","author":"Brunetti","year":"1991","journal-title":"Europhys. Lett."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB11","series-title":"Random Graphs","author":"Bollob\u00e0s","year":"1985"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB12","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.1006","article-title":"The scaling window of the 2-sat transition","volume":"18","author":"Bollob\u00e0s","year":"2001","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB13","volume":"vol. 2","author":"Cardy","year":"1988"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF00940812","article-title":"Thermodynamical approach to the traveling salesman problem","volume":"45","author":"\u010cerny","year":"1985","journal-title":"J. Optim. Theory Appl."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB15","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","article-title":"Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability","volume":"51","author":"Chao","year":"1990","journal-title":"Inform. Sci."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB16","doi-asserted-by":"crossref","unstructured":"V. Chv\u00e0tal, B. Reed, Mick gets some (the odds are on his side), in: Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992, p. 620.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB17","doi-asserted-by":"crossref","unstructured":"S. Cocco, R. Monasson, Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-satisfiability problem, Phys. Rev. Lett. 86 (2001) 1654, arXiv:cond-mat\/0009410.","DOI":"10.1103\/PhysRevLett.86.1654"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB18","doi-asserted-by":"crossref","unstructured":"S. Cook, The complexity of theorem-proving procedures, in: Proc. 3rd Ann. ACM Symp. on Theory of Computing, Assoc. Comput. Mach., New York, 1971, p. 151.","DOI":"10.1145\/800157.805047"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB19","doi-asserted-by":"crossref","first-page":"L775","DOI":"10.1088\/0305-4470\/22\/16\/003","article-title":"Replica symmetry breaking in finite connectivity systems","volume":"22","author":"Dominicis","year":"1989","journal-title":"J. Phys. A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB20","doi-asserted-by":"crossref","first-page":"L1267","DOI":"10.1088\/0305-4470\/20\/18\/009","article-title":"Replica symmetry breaking in weak connectivity systems","volume":"20","author":"Dominicis","year":"1987","journal-title":"J. Phys. A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB21","doi-asserted-by":"crossref","unstructured":"V. Dotsenko, Exact solution of the random bipartite matching model, J. Phys. A 33 (2000) 2015, cond-mat\/9911477.","DOI":"10.1088\/0305-4470\/33\/10\/305"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB22","doi-asserted-by":"crossref","unstructured":"T. Hogg, B.A. Huberman, C. Williams, (Eds.), Frontiers in problem solving: phase transitions and complexity, Artif. Intell. 81 (1996).","DOI":"10.1016\/0004-3702(95)00044-5"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB23","doi-asserted-by":"crossref","unstructured":"A. Engel, Complexity of learning in artificial neural networks, Theoret. Comput. Sci., this issue.","DOI":"10.1016\/S0304-3975(01)00167-0"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB24","series-title":"Spin glasses","author":"Fischer","year":"1991"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB25","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1088\/0305-4470\/19\/9\/033","article-title":"Application of statistical mechanics to NP-complete problems in combinatorial optimization","volume":"19","author":"Fu","year":"1986","journal-title":"J. Phys. A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB26","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB27","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1006\/jcss.1996.0081","article-title":"A threshold for unsatisfiability","volume":"53","author":"Goerdt","year":"1996","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB28","doi-asserted-by":"crossref","first-page":"L775","DOI":"10.1088\/0305-4470\/23\/15\/014","article-title":"The finite connectivity spin glass: investigation of replica symmetry breaking of the ground-state","volume":"23","author":"Goldschmidt","year":"1990","journal-title":"J. Phys. A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB29","doi-asserted-by":"crossref","unstructured":"A. Hartmann, M. Weigt, Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs, Theoret. Comput. Sci., this issue.","DOI":"10.1016\/S0304-3975(01)00163-3"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB30","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s100510050565","article-title":"Comparing mean field and Euclidean matching problems","volume":"6","author":"Houdayer","year":"1998","journal-title":"Eur. Phys. J. B"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB31","series-title":"Statistical Mechanics","author":"Huang","year":"1967"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB32","unstructured":"D.S. Johnson, L.A. McGeoch, E.E. Rothberg, Asymptotic experimental analysis for the Held-Karp traveling salesman bound, in: 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, 1996, pp. 341\u2013350."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB33","series-title":"Local Search in Combinatorial Optimization","first-page":"215","article-title":"The traveling salesman problem: A case study in local optimization","author":"Johnson","year":"1997"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB34","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1103\/PhysRevLett.58.164","article-title":"Mean-field theory of spin-glasses with finite coordination number","volume":"58","author":"Kanter","year":"1987","journal-title":"Phys. Rev. Lett."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB35","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/0208045","article-title":"A patching algorithm for the nonsymmetric travelling salesman problem","volume":"8","author":"Karp","year":"1979","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB36","first-page":"1114","volume":"26","author":"Kasteleyn","year":"1969","journal-title":"J. Phys. Soc. Japan Suppl."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB37","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB38","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1126\/science.264.5163.1297","article-title":"Critical behaviour in the satisfiability of random boolean expressions","volume":"264","author":"Kirkpatrick","year":"1994","journal-title":"Science"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB39","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1209\/0295-5075\/8\/3\/002","article-title":"The cavity method and the travelling-salesman problem","volume":"8","author":"Krauth","year":"1989","journal-title":"Europhys. Lett."},{"issue":"4","key":"10.1016\/S0304-3975(01)00149-9_BIB40","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1287\/opre.14.4.699","article-title":"Branch-and-bound methods: a survey","volume":"14","author":"Lawler","year":"1966","journal-title":"Oper. Res."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB41","doi-asserted-by":"crossref","unstructured":"M. Leone, F. Ricci-Tersenghi, R. Zecchina, Phase coexistence and finite size scaling in random combinatorial problems, J. Phys. A (2001) in press.","DOI":"10.1088\/0305-4470\/34\/22\/303"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB42","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","article-title":"Computer solutions of the traveling salesman problem","volume":"44","author":"Lin","year":"1965","journal-title":"Bell System Tech. J."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB43","series-title":"Statistical Mechanics","author":"Ma","year":"1985"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB44","doi-asserted-by":"crossref","unstructured":"S. Mertens, A physicist's approach to number partitioning, Theoret. Comput. Sci. 265 (this vol.) (2001) 79\u2013108.","DOI":"10.1016\/S0304-3975(01)00153-0"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB45","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1209\/0295-5075\/2\/12\/005","article-title":"Mean-field equations for the matching and the travelling salesman problem","volume":"2","author":"M\u00e9zard","year":"1986","journal-title":"Europhys. Lett."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB46","doi-asserted-by":"crossref","first-page":"1451","DOI":"10.1051\/jphys:019870048090145100","article-title":"On the solution of the random link matching problems","volume":"48","author":"M\u00e9zard","year":"1987","journal-title":"J. Phys."},{"issue":"10","key":"10.1016\/S0304-3975(01)00149-9_BIB47","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1209\/0295-5075\/3\/10\/002","article-title":"Mean-field theory of randomly frustrated systems with finite connectivity","volume":"3","author":"M\u00e9zard","year":"1987","journal-title":"Europhys. Lett."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB48","doi-asserted-by":"crossref","unstructured":"M. M\u00e9zard, G. Parisi, M.A. Virasoro (Eds.), Spin Glass Theory and Beyond, World Scientific, Singapore, 1987.","DOI":"10.1142\/0271"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB49","unstructured":"M. M\u00e9zard, G. Parisi, The Bethe lattice spin glass revisited, arXiv:cond-mat\/0009418."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB50","unstructured":"D. Mitchell, B. Selman, H. Levesque, Hard and easy distributions of sat problems, in: Proc. of Am. Assoc. for Artif. Intell. AAAI-92, 1992, pp. 456\u2013465."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB51","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1088\/0305-4470\/31\/2\/012","article-title":"Optimization problems and replica symmetry breaking in finite connectivity spin glasses","volume":"31","author":"Monasson","year":"1998","journal-title":"J. Phys. A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB52","doi-asserted-by":"crossref","first-page":"3881","DOI":"10.1103\/PhysRevLett.76.3881","article-title":"Entropy of the K-satisfiability problem","volume":"76","author":"Monasson","year":"1996","journal-title":"Phys. Rev. Lett."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB53","doi-asserted-by":"crossref","first-page":"1357","DOI":"10.1103\/PhysRevE.56.1357","article-title":"Statistical mechanics of the random K-Sat problem","volume":"56","author":"Monasson","year":"1997","journal-title":"Phys. Rev. E"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB54","doi-asserted-by":"crossref","first-page":"9209","DOI":"10.1088\/0305-4470\/31\/46\/011","article-title":"Tricritical points in random combinatorics: the (2+p)-SAT case","volume":"31","author":"Monasson","year":"1998","journal-title":"J. Phys. A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB55","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","article-title":"Computational complexity from \u2018characteristic\u2019 phase transitions","volume":"400","author":"Monasson","year":"1999","journal-title":"Nature"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB56","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<414::AID-RSA10>3.0.CO;2-G","article-title":"2+p-sat: Relation of typical-case complexity to thenature of the phase transition","volume":"3","author":"Monasson","year":"1999","journal-title":"Random Struct. Algorithms"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB57","unstructured":"A. Morgante, Large deviations in random graphs, Tech. Rep., Laboratoire de Physique Theorique de l'ENS, rapport de stage, 1998."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB58","doi-asserted-by":"crossref","first-page":"L375","DOI":"10.1088\/0305-4470\/20\/6\/007","article-title":"On the stability of randomly frustrated systems with finite connectivity","volume":"20","author":"Mottishaw","year":"1987","journal-title":"J. Phys. A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB59","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","article-title":"A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems","volume":"33","author":"Padberg","year":"1991","journal-title":"SIAM Rev."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB60","series-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB61","series-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB62","unstructured":"G. Parisi, A conjecture on random bipartite matching, cond-mat\/9801176 (1998)."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB63","doi-asserted-by":"crossref","first-page":"3775","DOI":"10.1088\/0305-4470\/26\/15\/026","article-title":"Several results on the finite-size corrections in the Sherrington\u2013Kirkpatrick spin glass model","volume":"26","author":"Parisi","year":"1993","journal-title":"J. Phys. A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB64","article-title":"Finite size and dimensional dependence in the Euclidean traveling salesman problem","volume":"1996","author":"Percus","year":"11881191","journal-title":"Phys. Rev. Lett."},{"issue":"5\/6","key":"10.1016\/S0304-3975(01)00149-9_BIB65","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1023\/A:1004570713967","article-title":"The stochastic traveling salesman problem","volume":"94","author":"Percus","year":"1999","journal-title":"J. Stat. Phys."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB66","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1017\/S0305004100027419","volume":"48","author":"Potts","year":"1952","journal-title":"Proc. Camb. Phil. Soc."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB67","series-title":"Finite Size Scaling and Numerical Simulations of Statistical Systems","author":"Privman","year":"1988"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB68","series-title":"Fundamentals of Statistical and Thermal Physics","author":"Reif","year":"1965"},{"issue":"3","key":"10.1016\/S0304-3975(01)00149-9_BIB69","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1002\/rsa.3240030302","article-title":"On the travelling salesperson problem in many dimensions","volume":"3","author":"Rhee","year":"1992","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"10.1016\/S0304-3975(01)00149-9_BIB70","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1287\/moor.12.1.177","article-title":"Martingale inequalities and NP-complete problems","volume":"12","author":"Rhee","year":"1987","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB71","doi-asserted-by":"crossref","unstructured":"F. Ricci-Tersenghi, M. Weigt, R. Zecchina, The simplest k-satisfiability model, Phys. Rev. E 63 (2001) 026702, arXiv:cond-mat\/0011181.","DOI":"10.1103\/PhysRevE.63.026702"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB72","doi-asserted-by":"crossref","unstructured":"H. Rieger, Frustrated systems: Ground state properties via combinatorial optimization, in: J. Kertesz, I. Kondor (Eds.), Advances in Computer Simulation, Lecture Notes in Physics, vol. 501, Springer, Heidelberg, 1998.","DOI":"10.1007\/BFb0105463"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB73","series-title":"Principle of Nucleic Acid Structure","author":"Saenger","year":"1984"},{"issue":"1","key":"10.1016\/S0304-3975(01)00149-9_BIB74","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/S1052623497321523","article-title":"Cut size statistics of graph bisection heuristics","volume":"10","author":"Schreiber","year":"1999","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB75","unstructured":"B. Selman, H. Kautz, B. Cohen, Local search strategies for satisfiability testing, in: Proc. of DIMACS, 1993, p. 661."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB76","series-title":"Probability Theory and Combinatorial Optimization","author":"Steele","year":"1997"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB77","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/S0378-4371(98)00540-8","article-title":"Phase coexistence in a single DNA molecule","volume":"263","author":"Strick","year":"1998","journal-title":"Physica A"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB78","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s004400050009","article-title":"Rigorous low temperature results for the p-spin mean field spin glass model","volume":"117","author":"Talagrand","year":"2000","journal-title":"Prob. Theory Related Fields"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB79","doi-asserted-by":"crossref","first-page":"L1145","DOI":"10.1051\/jphyslet:0198400450240114500","article-title":"On the statistical mechanics of optimization problems of the travelling salesman type","volume":"45","author":"Vannimenus","year":"1984","journal-title":"J. Phys. Lett."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB80","doi-asserted-by":"crossref","first-page":"3037","DOI":"10.1088\/0022-3719\/18\/15\/013","article-title":"Phase diagrams for dilute spin-glasses","volume":"18","author":"Viana","year":"1985","journal-title":"J. Phys. C"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB81","unstructured":"D. Wilson, The empirical values of the critical k-sat exponents are wrong 2000, preprint arXiv:math\/0005136."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB82","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1103\/RevModPhys.54.235","article-title":"The Potts model","volume":"54","author":"Wu","year":"1982","journal-title":"Rev. Mod. Phys."},{"key":"10.1016\/S0304-3975(01)00149-9_BIB83","doi-asserted-by":"crossref","unstructured":"A.P. Young (Ed.), Spin Glasses and Random Fields, World Scientific, Singapore, 1998.","DOI":"10.1142\/3517"},{"key":"10.1016\/S0304-3975(01)00149-9_BIB84","unstructured":"P. Young, Informatics \u2013 10 years back, 10 years ahead, celebration of the 10th anniversary of Schloss Dagstuhl."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001499?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501001499?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T19:10:25Z","timestamp":1681413025000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501001499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,8]]},"references-count":84,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,8]]}},"alternative-id":["S0304397501001499"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00149-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,8]]}}}