Karloff–Zwick algorithm: Difference between revisions

Revision as of 23:34, 29 December 2009

Revision as of 05:28, 13 February 2010

Line 1:

{{orphan|date=February 2010}}

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.

The '''Karloff-ZwickKarloff–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 6 ⟶ 8:

==External links==

* [http://citeseer.ist.psu.edu/114724.html CiteSeer page for this paper]

[http://citeseer.ist.psu.edu/114724.html CiteSeer page for this paper]

== References ==

<references/>

[[Category:Approximation algorithms]]

[[Category:Probabilistic complexity theory]]

{{algorithm-stub}}