Karloff–Zwick algorithm: Difference between revisions

Revision as of 02:36, 8 September 2012

Revision as of 07:28, 11 September 2012

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. [[Howard Karloff]] and [[Uri Zwick]] presented the algorithm in 1997.<ref name="Karloff">{{citation|last1=Karloff|first1= H.|last2= Zwick|first2= U. |contribution=A 7/8-approximation algorithm for MAX 3SAT?|title=[[Symposium on Foundations of Computer Science]]|Proc. 38th Annual Symposium on Foundations of Computer Science|year=1997|pages=406–415|doi=10.1109/SFCS.1997.646129}}.</ref>