Golden ratio approximation for MAX-2SAT
ID: golden-ratio-approximation-for-max-2sat
When each variable appears in at most one normalized singleton clause, satisfy that favored literal with probability and choose independent variables. Every proper binary clause is then satisfied with probability at least , and every singleton with probability . Maximize the common lower bound by , giving the reciprocal of the golden ratio. The method of conditional probabilities derandomizes the construction, obtaining approximation ratio . Tautologies are harmless; the singleton restriction must be applied after removing repeated literals within clauses.
New to topics? Read the docs here!