Karloff–Zwick algorithm: Difference between revisions

Revision as of 20:47, 19 November 2005

Revision as of 23:37, 20 November 2005

Line 4:

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

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

20-22 Oct. 1997 Page(s):406 - 415