The Karloff–Zwick algorithm, in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, is a
randomised Randomization is the process of making something random. Randomization is not haphazard; instead, a random process is a sequence of random variables describing a process whose outcomes do not follow a deterministic pattern, but follow an evolution d ...
approximation algorithm taking an instance of
MAX-3SAT Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
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
mathematical proof
A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proo ...
) that the algorithm achieves 7/8 of optimal even on unsatisfiable MAX-3SAT instances.
Howard Karloff and
Uri Zwick
Uri Zwick is an Israeli computer scientist and mathematician known for his work on graph algorithms, in particular on distances in graphs and on the color-coding technique for subgraph isomorphism. With Howard Karloff, he is the namesake of the ...
presented the algorithm in 1997.
[.]
The algorithm is based on
semidefinite programming Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of positive ...
. It can be derandomized using, e.g., the techniques from to yield a deterministic
polynomial-time algorithm with the same approximation guarantees.
Comparison to random assignment
For the related MAX-E3SAT problem, in which all clauses in the input 3SAT formula are guaranteed to have exactly three literals, the simple
randomized
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual ra ...
approximation algorithm which assigns a truth value to each variable independently and uniformly at random satisfies 7/8 of all clauses in expectation, irrespective of whether the original formula is satisfiable. Further, this simple algorithm can also be easily
derandomized using the
method of conditional expectations. The Karloff–Zwick algorithm, however, does not require the restriction that the input formula should have three literals in every clause.
Optimality
Building upon previous work on the
PCP theorem,
Johan Håstad
Johan Torkel Håstad (; born 19 November 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation ...
showed that, assuming P ≠ 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 in which each clause contains exactly three literals. Both the Karloff–Zwick algorithm and the above simple algorithm are therefore optimal in this sense.
[.]
References
{{DEFAULTSORT:Karloff-Zwick algorithm
Approximation algorithms
Randomized algorithms