1.0957-Approximation Algorithm for Random MAX-3SAT

Wenceslas Fernandez de la Vega; Marek Karpinski

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 1, page 95-103
  • ISSN: 0399-0559


We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.

How to cite


Fernandez de la Vega, Wenceslas, and Karpinski, Marek. "1.0957-Approximation Algorithm for Random MAX-3SAT." RAIRO - Operations Research 41.1 (2007): 95-103. <http://eudml.org/doc/250097>.

abstract = { We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances. },
author = {Fernandez de la Vega, Wenceslas, Karpinski, Marek},
journal = {RAIRO - Operations Research},
keywords = {Random satisfiability; approximate algorithms.},
language = {eng},
month = {6},
number = {1},
pages = {95-103},
publisher = {EDP Sciences},
title = {1.0957-Approximation Algorithm for Random MAX-3SAT},
url = {http://eudml.org/doc/250097},
volume = {41},
year = {2007},

AU - Fernandez de la Vega, Wenceslas
AU - Karpinski, Marek
TI - 1.0957-Approximation Algorithm for Random MAX-3SAT
JO - RAIRO - Operations Research
DA - 2007/6//
PB - EDP Sciences
VL - 41
IS - 1
SP - 95
EP - 103
AB - We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.
LA - eng
KW - Random satisfiability; approximate algorithms.
UR - http://eudml.org/doc/250097
ER -


  1. D. Achioptas, Setting two variables at a time yields a new lower bound for random 3-SAT, in Proc. 32th STOC (2000) 28–37.  
  2. N. Alon and J. Spencer, The Probabilistic Method. Wiley (1992).  
  3. P. Beame, R. Karp, T. Pitassi and M. Saks, On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas, in Proc. 30th STOC (1998) 561–571.  Zbl1028.68067
  4. O. Dubois, Y. Boufkhad and J. Mandler, Typical 3-SAT Formulae and the Satisfiability Threshold, in Proc. 11th ACM-SIAM SODA (2000) 126–127.  Zbl0959.68135
  5. O. Dubois, R. Monasson, B. Selman and R. Zecchina, eds, Phase Transitions in Combinatorial problems, Theor. Comput. Sci.265 (2001) Nos. 1–2.  
  6. J. Friedman, A. Goerdt, Recognizing more unsatisfiable random 3SAT instances efficiently, in Proc. 28th ICALP (2001) 310-321.  Zbl0986.68042
  7. U. Feige, Relations between Average Case Complexity and Approximation Complexity, in Proc. 34th ACM STOC (2002) 534–543  Zbl1192.68358
  8. 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)  
  9. E. Friedgut, Necessary and sufficient conditions for sharp thresholds of graph properties and the k-SAT problem. J. Amer. Math. Soc.12 (1999) 1017–1054.  Zbl0932.05084
  10. A. Frieze and S. Suen, Analysis of Two Simple Heuristics of a Random Instance of k-SAT, J. Algorithms20 (1996) 312–355.  Zbl0852.68038
  11. J. Gu, P.W. Purdom, J. Franco and B.J. Wah, Algorithms for the satisfiability (SAT) problem: A Survey, in Satisfiability (SAT) Problem, DIMACS, American Mathematical Society (1997) 19–151.  Zbl0945.03040
  12. J. Håstad, Some optimal innasproximability results, in Proc. 29th ACM STOC (1997) 1–10.  
  13. W. Hoeffding, Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc.58 (1964) 13–30.  Zbl0127.10602
  14. Y. Interian, Approximation Algorithm for Random MAX-kSAT, in International Conference on the Theory and Applications of Satisfiability testing (2004).  
  15. A. El Maftouhi and W. Fernandez de la Vega, In Random 3-SAT. Combin. Probab. Comput.4 (1995) 189–195.  Zbl0840.68051

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.