Karloff–Zwick algorithm: Difference between revisions

Revision as of 04:19, 7 March 2022

Revision as of 06:37, 26 July 2022

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. There is strong evidence (but not a [[mathematical proof]]) that the algorithm achieves 7/8 of optimal even on unsatisfiable 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. |chapter=A 7/8-approximation algorithm for MAX 3SAT?|title-link=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 can be derandomized using, e.g., the techniques from <ref>{{citation|last1=Sivakumar |first1=D. |title=Algorithmic derandomization via complexity theory |journal=Proceedings of the thiryThiry-fourth annualAnnual ACM symposiumSymposium on Theory of computingComputing |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.

==Comparison to random assignment==

Line 7:

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