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


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


Zbl 0820.68056