1.0957-Approximation Algorithm for Random MAX-3SAT
Wenceslas Fernandez de la Vega, Marek Karpinski (2007)
RAIRO - Operations Research
Similarity:
We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.