New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem

Yannakakis recently presented the first 3/4-approximation algorithm for the Maximum Satisfiability Problem (MAX SAT). His algorithm makes nontrivial use of solutions to maximum flow problems. New, simple 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 3/4 of the optimal solution. It is further shown that an unusual twist on randomized rounding also yields 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.