From the summary: H. Karloff and U. Zwick [Proc. 38rd Annual IEEE Symp. Foundations of Computer Science, Miami Beach, Florida, 406-415 (1997)] obtained recently an optimal 7/8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7/8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinite programming relaxation of MAX 4-SAT and a new family of rounding procedures that try to cope well with clauses of various sizes. We study the potential, and the limitations, of the relaxation and of the proposed family of rounding procedures using a combination of theoretical and experimental means. We select two rounding procedures from the proposed family of rounding procedures.
For the entire collection see [Zbl 0914.00106].