Karloff–Zwick algorithm: Difference between revisions

Revision as of 20:46, 19 November 2005

Revision as of 20:47, 19 November 2005

Line 3:

== Overview ==

The '''Karloff-Zwick algorithm''' in [[Computational complexity theory]] solves the [[MAX-3SAT]] problem in [[polynomial-time]] and satisfies &Gege; 7/8 [[3SAT]] clauses.

== 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

Digital Object Identifier 10.1109/SFCS.1997.646129

<!-- [[Category:Computational complexity theory]] -->