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

Goemans, Michel X.; Williamson, David P.

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

Keywords:

maximum satisfiability problem; \({3\over 4}\)-approximation algorithm; linear programming relaxation; worst-case analysis; duality gap

Citations:

Zbl 0820.68056