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. [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]

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

External links

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

References