# zbMATH — the first resource for mathematics

On the approximation of maximum satisfiability. (English) Zbl 0820.68056
Summary: We present a 3/4 polynomial time approximation algorithm for the maximum satisfiability problem: Given a set of clauses, find a truth assignment that satisfies the maximum number of clauses. The algorithm applies to the weighted case as well, and involves nontrivial application of network flow techniques.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 90C60 Abstract computational complexity for mathematical programming problems
##### Keywords:
maximum satisfiability; network flow techniques
Full Text: