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 explores the relationships between these classifications. A computational problem ...
, is a
randomised approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
taking an instance of
MAX-3SAT
MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as:
''Given a 3-CNF formula ...
Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisf ...
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 a deductive reasoning, deductive Argument-deduction-proof distinctions, argument for a Proposition, mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use othe ...
) that the algorithm achieves 7/8 of optimal even on unsatisfiable MAX-3SAT instances.
Howard Karloff
Howard is a masculine given name derived from the English surname Howard. ''The Oxford Dictionary of English Christian Names'' notes that "the use of this surname as a christian name is quite recent and there seems to be no particular reason for ...
and
Uri Zwick
Uri Zwick (Hebrew: אורי צוויק) 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 ...
presented the algorithm in 1997.
[.]
The algorithm is based on
semidefinite programming
Semidefinite programming (SDP) is a subfield of mathematical programming 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 po ...
. It can be derandomized using, e.g., the techniques from to yield a deterministic
polynomial-time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
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 approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
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
In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs ( proofs that can be checked by a randomiz ...
,
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