Jump to content

Karloff–Zwick algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Daverobe (talk | contribs) at 20:46, 19 November 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Overview

The Karloff-Zwick algorithm in Computational complexity theory solves the MAX-3SAT problem in polynomial-time and satisfies &Ge; 7/8 3SAT clauses.

References

A 7/8-approximation algorithm for MAX 3SAT? Karloff, H.; Zwick, U.; Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on 20-22 Oct. 1997 Page(s):406 - 415 Digital Object Identifier 10.1109/SFCS.1997.646129


Retrieved from "https://en.wikipedia.org/w/index.php?title=Karloff–Zwick_algorithm&oldid=28775062"