Best-of-Two Approximation Algorithm for Maximum Satisfiability

Definition

Best-of-Two Approximation Algorithm for Maximum Satisfiability

Given a MaxSAT instance $F$ with clauses $C_1,\dots ,C_m$, the best-of-two algorithm constructs two truth assignments:

• ${\sigma }_{\mathrm{rand}}$: set each variable independently to $1$ with probability $1/2$;
• ${\sigma }_{\mathrm{LP}}$: set each variable $x_i$ independently to $1$ with probability ${\hat{y}}_i$, where $(\hat{y},\hat{z})$ is an optimal solution of the LP relaxation below.

Return the assignment ${\sigma }^{\ast }$ satisfying more clauses. Writing ${\mathrm{val}}_F(\sigma )$ for the number of clauses satisfied by $\sigma$,

$$\mathbb{E}[{\mathrm{val}}_F({\sigma }^{\ast })]\ge \frac{3}{4}\mathrm{OPT}(F).$$

The algorithm runs in polynomial time; the guarantee is in expectation, not for every random outcome.

Choose one method uniformly

Instead of running both methods, toss one fair coin to choose between ${\sigma }_{\mathrm{rand}}$ and ${\sigma }_{\mathrm{LP}}$. This mixture has the same $3/4$ expected guarantee. Returning the better of both can only improve the expected value.

From Clauses to a Linear Programme

Let $x_1,\dots ,x_n$ be the variables. Remove repeated literals within each clause. A clause containing both $x_i$ and $\neg x_i$ is always satisfied (e.g., $C=(x_i\vee \neg x_i\vee \dots )$): set it aside and add its contribution back at the end. Empty clauses are never satisfied and can be discarded. Thus every remaining clause is nonempty and contains each variable at most once. This is what makes its literal outcomes independent under independent variable choices.

For clause $C_j$, write

$$P_j=\{i:x_i\in C_j\},N_j=\{i:\neg x_i\in C_j\},k_j=|P_j|+|N_j|.$$

Encode truth values and counted clauses

Introduce a binary variable $y_i$ for the truth value of $x_i$ and a binary variable $z_j$ indicating whether we count clause $C_j$ as satisfied. The integer linear programme is

$$\begin{array}{rlrl}\text{maximise}& \sum _{j=1}^m{z}_j& & \\ \text{subject to}& z_j\le \underset{\text{number of true literals in }{C}_j}{\underbrace{\sum _{i\in P_j}{y}_i+\sum _{i\in N_j}(1-y_i)}}& & (1\le j\le m),\\ & y_i\in \{0,1\}& & (1\le i\le n),\\ & z_j\in \{0,1\}& & (1\le j\le m).\end{array}$$

Each summand is a truth indicator, not merely a positive contribution:

• For a positive literal $x_i$, the term $y_i$ is $1$ exactly when $x_i$ is true.
• For a negative literal $\neg x_i$, the term $1-y_i$ is $1$ exactly when $x_i$ is false, so that $\neg x_i$ is true.

Thus all terms are non-negative, but they can all be zero. The two sums together count the true literals in $C_j$. For $C_j=(x_1\vee \neg x_2\vee x_3)$, inspect the actual entries:

Variable values $(y_1,y_2,y_3)$	Literal truth indicators $(y_1,1-y_2,y_3)$	Constraint	Allowed $z_j$
$(0,1,0)$	$(0,0,0)$	$z_j\le 0$	Only $0$
$(1,1,0)$	$(1,0,0)$	$z_j\le 1$	$0$ or $1$
$(1,0,1)$	$(1,1,1)$	$z_j\le 3$	Still only $0$ or $1$

The interesting restriction is the first row: we cannot claim a point for a false clause. Without this constraint, maximising ${\sum }_j{z}_j$ would simply set every $z_j=1$, even for clauses made false by the chosen assignment.

In the other rows, the clause is true and the constraint permits its point. It does not force $z_j=1$ by itself; the objective does that. For fixed binary values $y_1,\dots ,y_n$, maximising over $z_j$ gives

$$z_j=\min \left\{1,\underset{\text{number of true literals}}{\underbrace{\sum _{i\in P_j}{y}_i+\sum _{i\in N_j}(1-y_i)}}\right\}.$$

The binary bound on $z_j$ caps the reward at one, even if several literals are true. The inequality and the objective together therefore encode the clause’s OR: zero points if all literals are false, one point otherwise.

The same $y_i$ is shared by every occurrence of $x_i$. For example, the two clauses $(x_i)$ and $(\neg x_i)$ impose $z_1\le y_i$ and $z_2\le 1-y_i$, so $z_1+z_2\le 1$. We cannot count both contradictory clauses as satisfied. Hence maximising ${\sum }_j{z}_j$ really maximises the number of clauses satisfied by one consistent assignment, and the integer optimum is exactly $\mathrm{OPT}(F)$.

Relax the binary choices

Replace $y_i,z_j\in \{0,1\}$ by $0\le y_i,z_j\le 1$ and solve the resulting linear programme. Let $(\hat{y},\hat{z})$ be an optimal fractional solution and let

$$L=\sum _{j=1}^m{\hat{z}}_j.$$

Every integer solution remains feasible in the relaxation, so

$$L\ge \mathrm{OPT}(F).$$

The fractional value $L$ is an upper bound, not necessarily the value of any truth assignment. Rounding turns ${\hat{y}}_i$ into the probability of setting $x_i=1$; the variables ${\hat{z}}_j$ are used for the analysis, not sampled.

Algorithm

BestOfTwoMaxSAT(F):
    simplify clauses as described above
    solve the LP relaxation to obtain (ŷ, ẑ)
 
    for each variable xᵢ:
        σrand(xᵢ) ← 1 with probability 1/2, otherwise 0
        σLP(xᵢ)   ← 1 with probability ŷᵢ, otherwise 0
        use independent choices
 
    count the clauses satisfied by each assignment
    return whichever assignment satisfies more clauses

Every returned assignment is feasible: MaxSAT permits clauses to remain false. The issue is how many clauses are satisfied, not whether the assignment satisfies all of $F$.

Why the Two Methods Complement Each Other

Both coefficients come from asking the same question: what is the probability that every literal in one clause is false? Subtract that probability from $1$ to obtain the probability that the clause is satisfied. Fix a clause $C_j$ with $k=k_j$ literals on distinct variables.

Uniform sampling gives $a_k$

Every literal is false with probability $1/2$, whether it is positive or negative. Since the variable choices are independent,

$$\begin{array}{rl}\mathrm{Pr}[C_j\text{ false}]& =\underset{k\text{ false literals}}{\underbrace{\frac{1}{2}\cdot \frac{1}{2}\cdots \frac{1}{2}}}=2^{-k},\\ \mathrm{Pr}[C_j\text{ true}]& =1-2^{-k}=:a_k.\end{array}$$

Thus $a_k$ is an exact probability. For three literals, only one of the eight equally likely literal truth patterns makes all three false, so $a_3=7/8$.

LP rounding gives $b_k$

Now the literal truth probabilities $p_1,\dots ,p_k$ need not equal $1/2$. The LP constraint gives only
$\underset{\text{sum of literal truth probabilities}}{\underbrace{p_1+\cdots +p_k}}\ge {\hat{z}}_j.$
First consider ${\hat{z}}_j=1$. The LP claims a full point for this clause, but it need not make any individual literal certainly true. It may spread the required total $1$ evenly: $p_1=\cdots =p_k=1/k$.

This is the worst distribution for satisfying the clause under the constraint ${\sum }_r{p}_r\ge 1$: using total $1$ and distributing it evenly maximises the product of failure probabilities ${\prod }_r(1-p_r)$. The arithmetic–geometric mean argument below proves this. Consequently,

$$\begin{array}{rl}\mathrm{Pr}[C_j\text{ false}]& \le \underset{k\text{ failure probabilities}}{\underbrace{\left(1-\frac{1}{k}\right)\cdots \left(1-\frac{1}{k}\right)}}={\left(1-\frac{1}{k}\right)}^k,\\ \mathrm{Pr}[C_j\text{ true}]& \ge 1-{\left(1-\frac{1}{k}\right)}^k=:b_k.\end{array}$$

For three literals with truth probabilities $(1/3,1/3,1/3)$, the LP constraint allows ${\hat{z}}_j=1$, yet the clause fails with probability $(2/3{)}^3=8/27$. Its satisfaction probability is $19/27=b_3$, not $1$.

For a fractional claim $0\le {\hat{z}}_j\le 1$, the same argument gives the bound $1-(1-{\hat{z}}_j/k{)}^k$. Its concavity, proved below, yields

$$\mathrm{Pr}[C_j\text{ true under LP rounding}]\ge 1-{\left(1-\frac{{\hat{z}}_j}{k}\right)}^k\ge b_k{\hat{z}}_j.$$

Thus $b_k$ is a guaranteed fraction of the LP contribution ${\hat{z}}_j$, not the clause’s exact satisfaction probability in every LP solution. The probabilities $1/k$ explain the worst-case bound; the algorithm still uses the actual probabilities supplied by the LP.

To compare the methods, use the same reference quantity ${\hat{z}}_j$. Uniform sampling gives $a_k\ge a_k{\hat{z}}_j$ because ${\hat{z}}_j\le 1$; LP rounding gives at least $b_k{\hat{z}}_j$. Averaging the two methods therefore guarantees at least $\frac{1}{2}(a_k+b_k){\hat{z}}_j$ for this clause.

Clause length $k$	Uniform coefficient $a_k$	LP coefficient $b_k$	Average coefficient
$1$	$1/2$	$1$	$3/4$
$2$	$3/4$	$3/4$	$3/4$
$3$	$7/8$	$19/27$	$341/432\approx 0.789$
$k\to \infty$	$\to 1$	$\to 1-1/e$	$\to 1-1/(2e)\approx 0.816$

Long clauses give uniform sampling many chances to make a literal true. Short clauses give LP rounding a stronger guarantee relative to ${\hat{z}}_j$. The decreasing quantity $b_k$ is a bound coefficient, not a claim that every longer clause has a lower actual satisfaction probability.

Approximation Guarantee

Three-quarter guarantee

For every MaxSAT instance $F$, the uniform mixture and the best-of-two algorithm both satisfy

$$\mathbb{E}[{\mathrm{val}}_F(\sigma )]\ge \frac{3}{4}\mathrm{OPT}(F).$$

Proof

Bound the probability that LP rounding misses one clause

Fix a clause $C_j$ of length $k=k_j$. Let $p_1,\dots ,p_k$ be its literal truth probabilities: a positive literal $x_i$ has probability ${\hat{y}}_i$, and a negative literal $\neg x_i$ has probability $1-{\hat{y}}_i$.

LP feasibility gives ${\sum }_{r=1}^k{p}_r\ge {\hat{z}}_j$. The clause is false precisely when all its literals are false. Independence and the arithmetic–geometric mean inequality give

$$\begin{array}{rl}\mathrm{Pr}[C_j\text{ false under }{\sigma }_{\mathrm{LP}}]& =\prod _{r=1}^k(1-p_r)\\ & \le {\left(\frac{{\sum }_{r=1}^k(1-p_r)}{k}\right)}^k\\ & ={\left(1-\frac{{\sum }_{r=1}^k{p}_r}{k}\right)}^k\\ & \le {\left(1-\frac{{\hat{z}}_j}{k}\right)}^k.\end{array}$$

Thus the satisfaction probability is at least $f_k({\hat{z}}_j)$, where $f_k(z)=1-(1-z/k{)}^k$.

The function $f_k$ is concave on $[0,1]$: it is linear for $k=1$, and for $k\ge 2$,

$$f_k^{\prime \prime }(z)=-\frac{k-1}{k}{\left(1-\frac{z}{k}\right)}^{k-2}\le 0.$$

A concave function lies above the chord joining its endpoints. Since $f_k(0)=0$ and $f_k(1)=b_k$,

$$\underset{\text{rounded contribution}}{\underbrace{\mathrm{Pr}[C_j\text{ true under }{\sigma }_{\mathrm{LP}}]}}\ge f_k({\hat{z}}_j)\ge \underset{\text{fraction of LP contribution}}{\underbrace{b_k{\hat{z}}_j}}.$$

Average the two bounds for the same clause

Uniform sampling misses all $k$ literals with probability $2^{-k}$, so its satisfaction probability is $a_k$. Choosing one method with probability $1/2$ therefore gives

$$\begin{array}{rl}\mathrm{Pr}[C_j\text{ true under the mixture}]& \ge \frac{1}{2}(a_k+b_k{\hat{z}}_j)\\ & \ge \frac{1}{2}(a_k+b_k){\hat{z}}_j.\end{array}$$

The second inequality uses $0\le {\hat{z}}_j\le 1$. To bound the average coefficient, distinguish the clause lengths:

• $k=1$: $a_1+b_1=1/2+1=3/2$.
• $k=2$: $a_2+b_2=3/4+3/4=3/2$.
• $k\ge 3$: $a_k\ge 7/8$ and $b_k\ge 1-1/e>5/8$, so $a_k+b_k>3/2$.

Here $(1-1/k{)}^k\le e^{-1}$ gives the bound on $b_k$, and $e>8/3$ gives $1-1/e>5/8$. Consequently every clause contributes at least $\frac{3}{4}{\hat{z}}_j$ in expectation.

Sum the clause contributions

Linearity of expectation does not require different clauses to be independent. For the mixture assignment ${\sigma }_{\mathrm{mix}}$,

$$\begin{array}{rl}\mathbb{E}[{\mathrm{val}}_F({\sigma }_{\mathrm{mix}})]& =\sum _{j=1}^m\mathrm{Pr}[C_j\text{ true}]\\ & \ge \frac{3}{4}\sum _{j=1}^m{\hat{z}}_j=\frac{3}{4}L\\ & \ge \frac{3}{4}\mathrm{OPT}(F).\end{array}$$

For best-of-two, write $R={\mathrm{val}}_F({\sigma }_{\mathrm{rand}})$ and $Q={\mathrm{val}}_F({\sigma }_{\mathrm{LP}})$. For every pair of sampled assignments,

$$\max \{R,Q\}\ge \frac{R+Q}{2}.$$

Taking expectations gives the same lower bound for the returned assignment. Finally, if preprocessing set aside $t$ tautological clauses, these add $t$ to every assignment and to the optimum; $t\ge \frac{3}{4}t$ preserves the guarantee for the original formula.

Running Time and Derandomisation

Let $\ell ={\sum }_j{k}_j$ be the number of literal occurrences. The LP has $n+m$ variables, $m$ clause constraints, and $2(n+m)$ bound constraints. Its encoding has polynomial size, so an optimal rational solution can be found in polynomial time. After solving the LP, sampling uses $O(n)$ Bernoulli choices, and evaluating both assignments takes $O(n+m+\ell )$ time.

Exact sampling from rational probabilities can be implemented in expected polynomial time using unbiased random bits. The usual randomised algorithm description treats each Bernoulli choice as a sampling operation.

The guarantee can also be made deterministic by conditional expectation. For each of the two methods, fix variables one at a time, choosing the value that does not decrease the conditional expected number of satisfied clauses. Such a value exists because the current expectation is a weighted average of the two conditional expectations. Each expectation is computable by summing clause satisfaction probabilities from the remaining independent variables.

The maintained invariant is that the conditional expectation never decreases. Once all variables are fixed, that expectation equals the actual clause count. Derandomise both methods and return the better assignment: its value is at least the average of their original expectations, hence at least $\frac{3}{4}\mathrm{OPT}(F)$.

Example

Fractional satisfaction is not certain satisfaction

Consider the four clauses

$$(x_1\vee x_2),(x_1\vee \neg x_2),(\neg x_1\vee x_2),(\neg x_1\vee \neg x_2).$$

The LP solution ${\hat{y}}_1={\hat{y}}_2=1/2$ and ${\hat{z}}_1=\cdots ={\hat{z}}_4=1$ is feasible: each clause has total literal truth probability $1$. Thus $L=4$.

Nevertheless, every integral assignment makes exactly one clause false, so $\mathrm{OPT}(F)=3$. Both sampling methods are uniform here. Each clause is satisfied with probability $3/4$, and every sampled assignment satisfies three clauses.

The fractional value ${\hat{z}}_j=1$ does not mean that rounding will certainly satisfy $C_j$. Here the expected total is exactly $\frac{3}{4}L=3$, which is already optimal for the original instance.