×

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
PDF BibTeX XML Cite
Full Text: DOI