Karloff–Zwick algorithm: Difference between revisions

Revision as of 23:37, 20 November 2005

Revision as of 02:08, 4 December 2005

Line 3:

== Overview ==

The '''Karloff-Zwick algorithm''' in [[Computational complexity theory]] solvespresents thea randomised approximation algorithm taking an instance of [[MAX-3SAT]] problemas ininput. [[polynomial-time]] andIf satisfiesthe ≥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]] clausesinstances.

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

They present a randomised approximation algorithm taking an instance of [[MAX-3SAT]] as input. If the instance is satisfiable then the assignment is correct within 7/8 of optimal probability.

== References ==

Line 13:

Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on<p>

20-22 Oct. 1997 Page(s):406 - 415

J. Hastad. "Some optimal inapproximability results."

In proceedings of the 29th ACM STOC, 1-10, 1997

<!-- [[Category:Computational complexity theory]] -->