Karloff-Zwick Algorithm

The Karloff-Zwick algorithm is a randomized approximation algorithm for MAX-3SAT, a Boolean satisfiability problem in computational complexity theory in which the goal is to satisfy as many three-literal clauses as possible. Developed by Howard Karloff and Uri Zwick and presented in 1997, it relies on semidefinite programming and, on any satisfiable instance, finds an assignment whose expected weight is at least seven eighths of the optimal weight, matching a proven hardness-of-approximation bound. The algorithm can be derandomized into a deterministic polynomial-time algorithm with the same guarantee, and unlike simpler randomized methods it does not require every clause to contain exactly three distinct literals. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/