Karloff–Zwick algorithm: Difference between revisions

Revision as of 02:09, 4 December 2005

Revision as of 02:10, 4 December 2005

Line 5:

The '''Karloff-Zwick algorithm''' in [[Computational complexity theory]] presents a randomised approximation algorithm taking an instance of [[MAX-3SAT]] as input. If the instance is satisfiable then the expected weight of the assignment found is at least 7/8 of optimal. They provide strong evidence (but not a proof) that the algorithm performs equally well on arbitrary [[MAX-3SAT]] instances.

Hastad has shown that, assuming P ≠ NP, no polynomial-time algorithm for MAX 3SAT can achieve a performance ratio exceeding 7/8����8, even when restricted to satisfiable instances of the problem. Their algorithm is therefore optimal in this sense.

== References ==