Karloff–Zwick algorithm

<p>The Karloff–Zwick algorithm, in <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, is a <a href="/facts/Randomized_algorithm/Fngl1zgk">randomised</a> <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithm</a> taking an instance of <a href="/facts/MAX-3SAT/CXGU7IX3">MAX-3SAT</a> <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a> as input.  If the instance is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal.  There is strong evidence (but not a <a href="/facts/Mathematical_proof/7ECDrU80">mathematical proof</a>) that the algorithm achieves 7/8 of optimal even on unsatisfiable MAX-3SAT instances.  Howard Karloff and <a href="/facts/Uri_Zwick/q9cnA3EU">Uri Zwick</a> presented the algorithm in 1997.
</p><p>The algorithm is based on <a href="/facts/Semidefinite_programming/pFN25EKE">semidefinite programming</a>. It can be derandomized using, e.g., the techniques from  to yield a deterministic <a href="/facts/Polynomial-time/77T62gmf">polynomial-time</a> algorithm with the same approximation guarantees.
</p>

Karloff–Zwick algorithm open-in-new

Karloff–Zwick algorithm