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