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
Access Full Article
top
Abstract
topHow to cite
topFernandez 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>.
@article{FernandezdelaVega2007,
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},
}
TY - JOUR
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 -
References
top- D. Achioptas, Setting two variables at a time yields a new lower bound for random 3-SAT, in Proc. 32th STOC (2000) 28–37.
- N. Alon and J. Spencer, The Probabilistic Method. Wiley (1992).
- 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.
- O. Dubois, Y. Boufkhad and J. Mandler, Typical 3-SAT Formulae and the Satisfiability Threshold, in Proc. 11th ACM-SIAM SODA (2000) 126–127.
- O. Dubois, R. Monasson, B. Selman and R. Zecchina, eds, Phase Transitions in Combinatorial problems, Theor. Comput. Sci.265 (2001) Nos. 1–2.
- J. Friedman, A. Goerdt, Recognizing more unsatisfiable random 3SAT instances efficiently, in Proc. 28th ICALP (2001) 310-321.
- U. Feige, Relations between Average Case Complexity and Approximation Complexity, in Proc. 34th ACM STOC (2002) 534–543
- 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)
- 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.
- A. Frieze and S. Suen, Analysis of Two Simple Heuristics of a Random Instance of k-SAT, J. Algorithms20 (1996) 312–355.
- 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.
- J. Håstad, Some optimal innasproximability results, in Proc. 29th ACM STOC (1997) 1–10.
- W. Hoeffding, Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc.58 (1964) 13–30.
- Y. Interian, Approximation Algorithm for Random MAX-kSAT, in International Conference on the Theory and Applications of Satisfiability testing (2004).
- A. El Maftouhi and W. Fernandez de la Vega, In Random 3-SAT. Combin. Probab. Comput.4 (1995) 189–195.
NotesEmbed ?
topYou 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.