Karloff–Zwick algorithm: Difference between revisions

Revision as of 02:10, 4 December 2005

Revision as of 18:06, 22 August 2006

Line 1:

The '''Karloff-Zwick algorithm''', in [[Computationalcomputational complexity theory]], presentsis a 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. TheyIt provideprovides strong evidence (but not a [[mathematical proof]]) that the algorithm performs equally well on arbitrary [[MAX-3SAT]] instances.

__TOC__

[[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>

== Overview ==

Hastad[[Johan Håstad]] has shown that, assuming P &ne; 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.<ref>J. Hastad. "Some optimal inapproximability results." In proceedings of the 29th ''ACM STOC'', 1-10, 1997</ref>

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 &ne; 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.

== References ==

<references/>

A 7/8-approximation algorithm for MAX 3SAT?

Karloff, H., Zwick, U.<p>

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

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

<p>

J. Hastad. "Some optimal inapproximability results."

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

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