## A new $$\frac{3}{4}$$-approximation algorithm for $$\text{MAX SAT}$$.(English)Zbl 0929.90071

Rinaldi, Giovanni (ed.) et al., Integer programming and combinatorial optimization. Proceedings of a conference held at Centro Ettore Majorana, Erice, Italy, April 29 - May 1, 1993. Louvain-la-Neuve: Librarian CORE, 313-321 (1993).
Summary: Recently, M. Yannakakis [J. Algorithms 17, No. 3, 475-502 (1994; Zbl 0820.68056)] presented the first $${3\over 4}$$-approximation algorithm for the Maximum Satisfiability Problem (MAX SAT). His algorithm makes non-trivial use of solutions to max-flow problems. We present a new $${3\over 4}$$-approximation algorithm that depends solely on the solution to a linear programming relaxation of MAX SAT. The algorithm uses the probabilistic method/randomized rounding in an unusual way. As a by-product, we obtain a tight worst-case analysis of the corresponding duality gap.
For the entire collection see [Zbl 0908.00035].

### MSC:

 90C27 Combinatorial optimization 90C05 Linear programming 68Q25 Analysis of algorithms and problem complexity 90C60 Abstract computational complexity for mathematical programming problems

Zbl 0820.68056