Karloff–Zwick algorithm: Difference between revisions

Revision as of 05:10, 2 September 2008

Latest revision as of 19:44, 7 August 2023

(27 intermediate revisions by 14 users not shown)

Line 1:

The '''Karloff-ZwickKarloff–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 wellof optimal even 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. |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 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.

[[Howard Karloff]] and [[Uri Zwick]] presented the algorithm in 1997.<ref>Karloff, H., Zwick, U. "A 7/8-approximation algorithm for MAX 3SAT?". ''Foundations of Computer Science'', 1997. Proceedings., 38th Annual Symposium on 20-22 Oct. 1997 Pages: 406 - 415</ref>

==Comparison to random assignment==

[[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>J. Hastad. "Some optimal inapproximability results." In proceedings of the 29th ''ACM STOC'', 1-10, 1997</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"/>

==External linksOptimality==

Building upon previous work on the [[PCP theorem]], [[Johan Håstad]] has shownshowed 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. TheirBoth the Karloff–Zwick algorithm isand the above simple algorithm are 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,.1145/502090.502098|pages=798–859|citeseerx=10.1.1.638.2808|s2cid=5120748 1997}}.</ref>

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

== References ==

{{reflist}}

<references/>

[[Category:Computational complexity theory]]

{{DEFAULTSORT:Karloff-Zwick algorithm}}

{{comp-sci-stub}}

[[Category:Approximation algorithms]]

[[Category:Randomized algorithms]]