= Golden ratio approximation for MAX-2SAT
{title2=$p=(\sqrt5-1)/2$}
When each variable appears in at most one normalized singleton <clause>, satisfy that favored <literal> with <probability> $p>1/2$ and choose independent variables. Every proper binary <clause> is then satisfied with <probability> at least $1-p^2$, and every singleton with <probability> $p$. Maximize the common lower bound by $p=1-p^2$, giving the reciprocal of the <golden ratio>. The <method of conditional probabilities> derandomizes the construction, obtaining <approximation ratio> $p$. Tautologies are harmless; the singleton restriction must be applied after removing repeated <literals> within <clauses>.
Back to article page
