Karloff–Zwick algorithm
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. 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.[1]
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.[2]
References
- ^ Karloff, H.; Zwick, U. (1997), "A 7/8-approximation algorithm for MAX 3SAT?", Symposium on Foundations of Computer Science, pp. 406–415, doi:10.1109/SFCS.1997.646129
{{citation}}: Text "Proc. 38th Annual Symposium on Foundations of Computer Science" ignored (help). - ^ Hastad, J. (2001), "Some optimal inapproximability results", Journal of the ACM, 48 (4), doi:10.1145/502090.502098.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |