Karloff–Zwick algorithm: Difference between revisions

Revision as of 18:46, 27 December 2006

Revision as of 00:29, 24 March 2008

Line 4:

[[Johan Håstad]] has shown that, assuming P &ne; 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.<ref>J. Hastad. "Some optimal inapproximability results." In proceedings of the 29th ''ACM STOC'', 1-10, 1997</ref>

== External Links ==

[[http://citeseer.ist.psu.edu/114724.html|CiteSeer's page for this paper]]

== References ==