Jump to content

Karloff–Zwick algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by RobinK (talk | contribs) at 05:28, 13 February 2010 (clean up, added orphan tag using AWB). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

  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


Stub icon

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Karloff–Zwick_algorithm&oldid=343676231"