Jump to content

Karloff–Zwick algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 68.40.61.102 (talk) at 23:37, 20 November 2005. 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 solves the MAX-3SAT problem in polynomial-time and satisfies ≥ 7/8 3SAT clauses.

They present a randomised approximation algorithm taking an instance of MAX-3SAT as input. If the instance is satisfiable then the assignment is correct within 7/8 of optimal probability.

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

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