1.0957-Approximation Algorithm for Random MAX-3SAT
CNRS, université Paris Sud, Orsay, France; email@example.com
2 Dept. of Computer Science, University of Bonn, Germany; firstname.lastname@example.org
Accepted: 16 October 2006
We prove that MAX-3SAT can be approximated in polynomial time within a factor 1.0957 on random instances.
Mathematics Subject Classification: 68W25 / 03B70
Key words: Random satisfiability / approximate algorithms.
© EDP Sciences, ROADEF, SMAI, 2007