Karloff-Zwick algorithm

From Wikipedia, the free encyclopedia

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]

[edit] External Links

CiteSeer page for this paper

[edit] References

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


Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.