Jump to content

Karloff–Zwick algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Daverobe (talk | contribs) at 02:08, 4 December 2005 (added detail and a reference). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Overview

The Karloff-Zwick algorithm in Computational complexity theory presents a randomised approximation algorithm taking an instance of MAX-3SAT as input. If the instance is satisfiable then the expected weight of the assignment found is at least 7/8 of optimal. They provide strong evidence (but not a proof) that the algorithm performs equally well on arbitrary MAX-3SAT instances.

Hastad 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.

References

A 7/8-approximation algorithm for MAX 3SAT?

Karloff, H., Zwick, U.

Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on

20-22 Oct. 1997 Page(s):406 - 415 J. Hastad. "Some optimal inapproximability results." In proceedings of the 29th ACM STOC, 1-10, 1997

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