Assignment-and-Complement Algorithm (MaxSAT)

Definition

Assignment-and-Complement Algorithm (MaxSAT)

For a MaxSAT formula $F$ with $m$ non-empty clause, choose any truth assignment $a$ and let $\bar{a}$ flip every variable. Write $s_F(a)$ for the number of clauses satisfied by $a$. Return

$$A(F):=\{\begin{array}{ll}a,& s_F(a)\ge m/2,\\ \bar{a},& s_F(a)<m/2.\end{array}$$

This is a deterministic $0.5$-constant-factor approximation algorithm: the returned assignment satisfies at least half as many clauses as an optimal assignment.

The assignments are like two sides of a coin, but the choice is not random: keep $a$ if it reaches half; otherwise use $\bar{a}$. A clause can be satisfied on both sides.

Why One Half Is Guaranteed

Approximation guarantee

$$s_F(A(F))\ge \frac{m}{2}\ge \frac{\mathrm{OPT}(F)}{2}.$$

Proof

Every non-empty clause contains a literal. That literal is true under either $a$ or $\bar{a}$, so the clause is satisfied by at least one of them. Counting over all clauses gives

$$\begin{array}{rl}\underset{\text{total satisfied across both assignments}}{\underbrace{s_F(a)+s_F(\bar{a})}}& \ge m,\\ \underset{\text{average}}{\underbrace{\frac{s_F(a)+s_F(\bar{a})}{2}}}& \ge \frac{m}{2},\\ \underset{\text{better assignment}}{\underbrace{\max \{s_F(a),s_F(\bar{a})\}}}& \ge \frac{m}{2}.\end{array}$$

The algorithm need not identify the better assignment: if $a$ already reaches $m/2$, keep it. Otherwise,

$$s_F(\bar{a})\ge m-s_F(a)>m/2.$$

In either case, the output satisfies at least $m/2$ clauses. Since $\mathrm{OPT}(F)\le m$, this is at least half the optimum.

Complexity and Scope

Counting satisfied clauses takes $O(L)$ time, where $L$ is the total number of literal occurrences. Creating and, if necessary, complementing an assignment takes $O(n)$ time for $n$ variables. Total time is $O(n+L)$, with $O(n)$ space for the assignment.

Empty clauses are never satisfiable: discard them before counting $m$. This leaves the optimum unchanged. The argument concerns unweighted MaxSAT; for non-negative clause weights, replace clause counts by total satisfied weight throughout.

Example

Flipping reaches the bound

Let $F=(x)\wedge (y)\wedge (z)\wedge (\neg x)$. The all-false assignment satisfies only $(\neg x)$, so $s_F(a)=1<4/2$.

Its complement satisfies $(x),(y),(z)$, giving $s_F(\bar{a})=3$. The optimum is also $3$: the clauses $(x)$ and $(\neg x)$ cannot both be satisfied.