Karloff–Zwick algorithm: Difference between revisions
sectionize and unstub |
Citation bot (talk | contribs) m Alter: title. Add: citeseerx, isbn, chapter. | You can use this bot yourself. Report bugs here. | User-activated. |
||
| Line 1: | 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 performs equally well on arbitrary MAX-3SAT instances. [[Howard Karloff]] and [[Uri Zwick]] presented the algorithm in 1997.<ref name="Karloff">{{citation|last1=Karloff|first1= H.|last2= Zwick|first2= U. | |
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 performs equally well on arbitrary 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?|work= 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}}.</ref> |
||
==Comparison to random assignment== |
==Comparison to random assignment== |
||
| Line 5: | Line 5: | ||
==Optimality== |
==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}}.</ref> |
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}}.</ref> |
||
== References == |
== References == |
||
Revision as of 14:27, 10 February 2019
The Karloff–Zwick algorithm, in computational complexity theory, is a 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 performs equally well on arbitrary MAX-3SAT instances. Howard Karloff and Uri Zwick presented the algorithm in 1997.[1]
Comparison to random assignment
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 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 derandomized using the 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.[1]
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.[2]
References
- ^ a b Karloff, H.; Zwick, U. (1997), "Proceedings 38th Annual Symposium on Foundations of Computer Science", Proc. 38th Annual Symposium on Foundations of Computer Science, pp. 406–415, CiteSeerX 10.1.1.51.1351, doi:10.1109/SFCS.1997.646129, ISBN 978-0-8186-8197-4
{{citation}}:|chapter=ignored (help). - ^ Hastad, J. (2001), "Some optimal inapproximability results", Journal of the ACM, 48 (4): 798–859, CiteSeerX 10.1.1.638.2808, doi:10.1145/502090.502098.