New 3⁄4 - Approximation Algorithms for MAX SAT

Abstract

Recently, Yannakakis presented the first 3/4-approximation algorithm for the Maximum Satisfiability Problem (MAX SAT). His algorithm makes non-trivial use of solutions to maximum flow problems. We present new, simple 3/4-approximation algorithms that apply the probabilistic method/randomized rounding to the solution to a linear programming relaxation of MAX SAT. We show 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. We further show that an unusual twist on randomized rounding also yields 3/4-approximation algorithms. As a by-product of our analysis, we obtain a tight worst-case analysis of the relative duality gap of the linear programming relaxation.