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:47, 19 November 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Overview

The Karloff-Zwick algorithm in Computational complexity theory solves the MAX-3SAT problem in polynomial-time and satisfies ≥ 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


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