Karloff–Zwick algorithm: Difference between revisions

Revision as of 05:10, 2 September 2008

Revision as of 03:10, 13 November 2008

Line 1:

The '''Karloff-Zwick algorithm''', in [[computational complexity theory]], is a [[randomized algorithm|randomised]] [[approximation algorithm]] taking an instance of [[MAX-3SAT]] [[Boolean satisfiability problem]] as input. If the instance is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal. It provides strong evidence (but not a [[mathematical proof]]) that the algorithm performs equally well on arbitrary MAX-3SAT instances.

[[Howard Karloff]] and [[Uri Zwick]] presented the algorithm in 1997.<ref>Karloff, H., Zwick, U. "A 7/8-approximation algorithm for MAX 3SAT?". ''Foundations of Computer Science'', 1997. Proceedings., 38th Annual Symposium on 20-22 Oct. 1997 Pages: 406 - 415</ref>

Line 13:

[[Category:ComputationalApproximation complexity theoryalgorithms]]

[[Category:Probabilistic complexity theory]]

{{comp-sci-stub}}