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

TLDR

Yannakakis recently presented the first 3/4‑approximation algorithm for MAX SAT. The authors present new, simple 3/4‑approximation algorithms using probabilistic method/randomized rounding on a linear programming relaxation of MAX SAT. The algorithms employ maximum flow solutions and probabilistic method/randomized rounding on a linear programming relaxation of MAX SAT. The authors show that the best of randomized rounding and Johnson’s algorithm achieves a 3/4‑approximation, an unconventional randomized rounding variant yields a 4‑approximation, and they provide a tight worst‑case analysis of the LP relaxation’s duality gap.

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 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.