{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T19:19:19Z","timestamp":1669317559043},"reference-count":15,"publisher":"EDP Sciences","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2007,1]]},"DOI":"10.1051\/ro:2007008","type":"journal-article","created":{"date-parts":[[2007,4,4]],"date-time":"2007-04-04T14:55:41Z","timestamp":1175698541000},"page":"95-103","source":"Crossref","is-referenced-by-count":2,"title":["1.0957-Approximation Algorithm for Random MAX-3SAT"],"prefix":"10.1051","volume":"41","author":[{"given":"Wenceslas","family":"Fernandez de la Vega","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2007,6,15]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"D. Achioptas, Setting two variables at a time yields a new lower bound for random 3-SAT, inProc. 32th STOC(2000) 28\u201337.","DOI":"10.1145\/335305.335309"},{"key":"R2","unstructured":"N. Alon and J. Spencer,The Probabilistic Method. Wiley (1992)."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Karp, T. Pitassi and M. Saks, On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas, inProc. 30th STOC(1998) 561\u2013571.","DOI":"10.1145\/276698.276870"},{"key":"R4","unstructured":"O. Dubois, Y. Boufkhad and J. Mandler, Typical 3-SAT Formulae and the Satisfiability Threshold, inProc. 11th ACM-SIAM SODA(2000) 126\u2013127."},{"key":"R5","unstructured":"O. Dubois, R. Monasson, B. Selman and R. Zecchina, eds, Phase Transitions in Combinatorial problems,Theor. Comput. Sci.265(2001) Nos. 1\u20132."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"J. Friedman, A. Goerdt, Recognizing more unsatisfiable random 3SAT instances efficiently, inProc. 28th ICALP(2001) 310-321.","DOI":"10.1007\/3-540-48224-5_26"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"U. Feige, Relations between Average Case Complexity and Approximation Complexity, inProc. 34th ACM STOC(2002) 534\u2013543","DOI":"10.1145\/509907.509985"},{"key":"R8","unstructured":"W. Fernandez de la Vega and Marek Karpinski,9\/8 Approximation Algorithm for Random MAX-3SAT, ECCC tracts, TR02-070, Dec. 13 (2002). Revision accepted Jan. 10 (2003)"},{"key":"R9","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"Friedgut","year":"1999","journal-title":"J. Amer. Math. Soc."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Frieze and S. Suen, Analysis of Two Simple Heuristics of a Random Instance of k-SAT,J.\u00a0Algorithms20(1996) 312\u2013355.","DOI":"10.1006\/jagm.1996.0016"},{"key":"R11","unstructured":"J. Gu, P.W. Purdom, J. Franco and B.J. Wah, Algorithms for the satisfiability (SAT) problem: A Survey, inSatisfiability (SAT) Problem, DIMACS, American Mathematical Society (1997) 19\u2013151."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some optimal innasproximability results, inProc. 29th ACM STOC(1997) 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"R13","doi-asserted-by":"crossref","first-page":"13","DOI":"10.2307\/2282952","volume":"58","author":"Hoeffding","year":"1964","journal-title":"J. Amer. Statist. Assoc."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Y. Interian, Approximation Algorithm for Random MAX-kSAT, in International Conference on the Theory and Applications of Satisfiability testing (2004).","DOI":"10.1007\/11527695_14"},{"key":"R15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1017\/S0963548300001590","volume":"4","author":"El Maftouhi","year":"1995","journal-title":"Combin. Probab. Comput."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro:2007008\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T03:07:50Z","timestamp":1556334470000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro:2007008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":15,"journal-issue":{"issue":"1"},"alternative-id":["ro0521"],"URL":"https:\/\/doi.org\/10.1051\/ro:2007008","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}