We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.
Mots-clés : random satisfiability, approximate algorithms
@article{RO_2007__41_1_95_0, author = {Fernandez de La Vega, Wenceslas and Karpinski, Marek}, title = {1.0957 - {Approximation} algorithm for {Random} {MAX-3SAT}}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {95--103}, publisher = {EDP-Sciences}, volume = {41}, number = {1}, year = {2007}, doi = {10.1051/ro:2007008}, mrnumber = {2310542}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro:2007008/} }
TY - JOUR AU - Fernandez de La Vega, Wenceslas AU - Karpinski, Marek TI - 1.0957 - Approximation algorithm for Random MAX-3SAT JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2007 SP - 95 EP - 103 VL - 41 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2007008/ DO - 10.1051/ro:2007008 LA - en ID - RO_2007__41_1_95_0 ER -
%0 Journal Article %A Fernandez de La Vega, Wenceslas %A Karpinski, Marek %T 1.0957 - Approximation algorithm for Random MAX-3SAT %J RAIRO - Operations Research - Recherche Opérationnelle %D 2007 %P 95-103 %V 41 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2007008/ %R 10.1051/ro:2007008 %G en %F RO_2007__41_1_95_0
Fernandez de La Vega, Wenceslas; Karpinski, Marek. 1.0957 - Approximation algorithm for Random MAX-3SAT. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 1, pp. 95-103. doi : 10.1051/ro:2007008. http://www.numdam.org/articles/10.1051/ro:2007008/
[1] Setting two variables at a time yields a new lower bound for random 3-SAT, in Proc. 32th STOC (2000) 28-37.
,[2] The Probabilistic Method. Wiley (1992). | MR | Zbl
and ,[3] On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas, in Proc. 30th STOC (1998) 561-571. | Zbl
, , and ,[4] Typical 3-SAT Formulae and the Satisfiability Threshold, in Proc. 11th ACM-SIAM SODA (2000) 126-127. | Zbl
, and ,[5] Phase Transitions in Combinatorial problems, Theor. Comput. Sci. 265 (2001) Nos. 1-2. | Zbl
, , and , eds,[6] Recognizing more unsatisfiable random 3SAT instances efficiently, in Proc. 28th ICALP (2001) 310-321. | MR | Zbl
, ,[7] Relations between Average Case Complexity and Approximation Complexity, in Proc. 34th ACM STOC (2002) 534-543
,[8]
and Marek Karpinski, 9/8 Approximation Algorithm for Random MAX-3SAT, ECCC tracts, TR02-070, Dec. 13 (2002). Revision accepted Jan. 10 (2003)[9] Necessary and sufficient conditions for sharp thresholds of graph properties and the k-SAT problem. J. Amer. Math. Soc. 12 (1999) 1017-1054. | Zbl
,[10] Analysis of Two Simple Heuristics of a Random Instance of k-SAT, J. Algorithms 20 (1996) 312-355. | Zbl
and ,[11] Algorithms for the satisfiability (SAT) problem: A Survey, in Satisfiability (SAT) Problem, DIMACS, American Mathematical Society (1997) 19-151. | Zbl
, , and ,[12] Some optimal innasproximability results, in Proc. 29th ACM STOC (1997) 1-10. | Zbl
,[13] Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1964) 13-30. | Zbl
,[14] Approximation Algorithm for Random MAX-kSAT, in International Conference on the Theory and Applications of Satisfiability testing (2004). | Zbl
,[15] In Random 3-SAT. Combin. Probab. Comput. 4 (1995) 189-195. | Zbl
and ,Cité par Sources :