Karloff–Zwick algorithm: Difference between revisions

Revision as of 00:54, 11 December 2016

Revision as of 00:28, 6 July 2017

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]]|journaltitle= 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–Zwick algorithm, however, does not require the restriction that the input formula should have three literals in every clause.<ref name="Karloff"/>