New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem

Abstract

Yannakakis recently presented the first $\frac{3}{4}$-approximation algorithm for the Maximum Satisfiability Problem (MAX SAT). His algorithm makes nontrivial use of solutions to maximum flow problems. New, simple $\frac{3}{4}$-approximation algorithms that apply the probabilistic method/randomized rounding to the solution to a linear programming relaxation of MAX SAT are presented. It is shown that although standard randomized rounding does not give a good approximate result, the best solution of the two given by randomized rounding and a well-known algorithm of Johnson is always within $\frac{3}{4}$ of the optimal solution. It is further shown that an unusual twist on randomized rounding also yields $\frac{3}{4}$-approximation algorithms. As a by-product of the analysis, a tight worst-case analysis of the relative duality gap of the linear programming relaxation is obtained.