Karloff–Zwick algorithm: Difference between revisions

Revision as of 07:28, 11 September 2012

Revision as of 14:17, 20 April 2013

Line 1:

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>

For the related MAX-E3SAT problem, in which all clauses in the input 3SAT formula are guaranteed to have exactly three literals, the simple [[randomized algorithm|randomized]] [[approximation algorithm]] which assigns a truth value to each variable independently and uniformly at random satisfies 7/8 of all clauses in expectation, irrespective of whether the original formula is satisfiable. Further, this simple algorithm can also be easily [[Randomized_algorithm#Derandomization|derandomized]] using the [[Method_of_conditional_probabilities#The_method_of_conditional_probabilities_with_conditional_expectations|method of conditional expectations]]. The Karloff-ZwickKarloff–Zwick algorithm, however, does not require the restriction that the input formula should have three literals in every clause.<ref name="Karloff"/>

Building upon previous work on the [[PCP theorem]], [[Johan Håstad]] showed 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 in which each clause contains exactly three literals. Both the Karloff-ZwickKarloff–Zwick algorithm and the above simple algorithm are therefore optimal in this sense.<ref>{{citation|first=J.|last=Hastad|title=Some optimal inapproximability results|journal=[[Journal of the ACM]]|volume=48|issue=4|year=2001|doi=10.1145/502090.502098|pages=798–859}}.</ref>

== References ==

{{reflist}}

{{DEFAULTSORT:Karloff-Zwick algorithm}}

[[Category:Approximation algorithms]]

[[Category:Probabilistic complexity theory]]