Karloff–Zwick algorithm: Difference between revisions

Revision as of 08:21, 19 January 2011

Revision as of 03:37, 19 May 2011

Line 5:

[[Howard Karloff]] and [[Uri Zwick]] presented the algorithm in 1997.<ref>{{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>

[[Johan Håstad]] has shown 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. Their algorithm is 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 ==