Karloff–Zwick algorithm: Difference between revisions

Revision as of 05:28, 13 February 2010

Revision as of 08:21, 19 January 2011

Line 3:

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>{{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'', 1997. Proceedings]]|Proc., 38th Annual Symposium on 20-22Foundations Oct.of 1997Computer Pages: 406 - 415Science|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." In proceedings|journal=[[Journal of the 29th ''ACM STOC'', 1-]]|volume=48|issue=4|year=2001|doi=10, 1997.1145/502090.502098}}.</ref>

==External links==

* [http://citeseer.ist.psu.edu/114724.html CiteSeer page for this paper]

== References ==

{{reflist}}

<references/>

[[Category:Approximation algorithms]]