Karloff–Zwick algorithm: Difference between revisions

Revision as of 07:28, 11 September 2012

Latest revision as of 19:44, 7 August 2023

(19 intermediate revisions by 11 users not shown)

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. ItThere providesis strong evidence (but not a [[mathematical proof]]) that the algorithm performsachieves equally7/8 of optimal welleven on arbitraryunsatisfiable MAX-3SAT instances. [[Howard Karloff]] and [[Uri Zwick]] presented the algorithm in 1997.<ref name="Karloff">{{citation|last1=Karloff|first1= H.|title= Proceedings 38th Annual Symposium on Foundations of Computer Science|last2= Zwick|first2= U. |contributionchapter=A 7/8-approximation algorithm for MAX 3SAT?|title-link=[[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|isbn= 978-0-8186-8197-4|citeseerx= 10.1.1.51.1351|s2cid= 15447333}}.</ref>

The algorithm is based on [[semidefinite programming]]. It can be derandomized using, e.g., the techniques from <ref>{{citation|last1=Sivakumar |first1=D. |title=Proceedings of the thiry-fourth annual ACM symposium on Theory of computing |chapter=Algorithmic derandomization via complexity theory |date=19 May 2002 |pages=619–626 |doi=10.1145/509907.509996|isbn=1581134959 |s2cid=94045 }}</ref> to yield a deterministic [[polynomial-time]] algorithm with the same approximation guarantees.

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"/>

==Comparison to random assignment==

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

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"/>

==Optimality==

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|citeseerx=10.1.1.638.2808|s2cid=5120748 }}.</ref>

== References ==

{{reflist}}

{{DEFAULTSORT:Karloff-Zwick algorithm}}

[[Category:Approximation algorithms]]

[[Category:ProbabilisticRandomized complexity theoryalgorithms]]

{{algorithm-stub}}