NEW 3 4-APPROXIMATION ALGORITHMS FOR THE MAXIMUM SATISFIABILITY PROBLEM/

Yannakakis recently presented the first 3/4-approximation algorithm fo r the Maximum Satisfiability Problem (MAX SAT). His algorithm makes no ntrivial use of solutions to maximum flow problems. New, simple 3/4-ap proximation 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 well-known algorithm of Johnson is a lways within 3/4 of the optimal solution. It is further shown that an unusual twist on randomized rounding also yields 3/4-approximation alg orithms. As a by-product of the analysis, a tight worst-case analysis of the relative duality gap of the linear programming relaxation is ob tained.