The problem and its assumptions
Definition 6.1.1
(Weighted Max-2SAT)
A Boolean variable is either true or false; a literal is a variable or its negation. An assignment satisfies a clause when at least one of its literals is true. Here every clause has exactly two literals on different variables, and each clause has a nonnegative rational weight encoded in binary. Repeated clauses are allowed and contribute separately. Write for the sum of the weights, and for the maximum satisfied weight over all assignments.
These notes maximize weight; they do not promise that all clauses can be satisfied.
A random assignment
Assign each variable independently and uniformly to true or false. Let indicate that clause , of weight , is satisfied; the satisfied weight is .
Theorem 6.1.2
(Expected weight of a random assignment)
Under the assumptions above, . Consequently some assignment has satisfied weight at least .
Proof
(Linearity of expectation over the clauses)
Both literals of a clause are false with probability , because they sit on different variables and those variables are independent fair bits. So each clause is satisfied with probability , and linearity of expectation gives
The clause indicators can be dependent: for example, two clauses may share a variable. Linearity does not require their independence. Since weights are nonnegative, , hence . In particular, some assignment has weight at least : otherwise the average of the finitely many assignment values would be smaller.
Derandomization by conditional expectation
Definition 6.1.3
(Conditional expectation of a partial assignment)
For a partial assignment , let be the expected satisfied weight when every unassigned variable is still independently uniform. Then , and for a complete assignment is its satisfied weight.
Theorem 6.1.4
(Deterministic guarantee)
There is a deterministic polynomial-time algorithm that outputs an assignment of satisfied weight at least , and consequently at least , under the assumptions above.
Proof
(Choosing the better branch never lowers the conditional expectation)
Fix the variables one at a time. For the next variable , the law of total expectation says
At least one of the two conditional expectations is at least . Choose such a value and continue. Initially ; after the final choice no randomness remains and equals the actual satisfied weight. Thus the value never falls below the initial expectation.
Each is computed clause by clause. A clause already made true contributes its full weight ; a clause with both literals fixed false contributes ; otherwise distinct variables of the clause are unset and no literal is true, and the clause contributes , that is or . With variables and clauses, each step evaluates two sums of such terms, so the run uses additions and multiplications on rationals. Their common denominator divides four times a common denominator of the weights, so the bit length stays polynomial in the input size.
Proof X-ray
Compute the potential rather than guess
The invariant is the whole proof: is the average of its two children, so a child at least as good exists, and at the end is the actual weight. Two details turn this from an existence statement into an algorithm. First, can be evaluated exactly without enumerating assignments, because the unset variables of one clause are independent of the fixed ones: a clause with no true literal and unset distinct variables is false with probability exactly . Second, ties may be broken arbitrarily, since the argument needs only that the chosen child is at least the average. The distinct-variable hypothesis matters here too: if a clause repeated a variable, would have to count distinct variables rather than literals.
Worked examples
Worked example 6.1.5
(Follow the conditional values)
Consider of weight , of weight , and of weight . Here and initially . Setting true gives ; setting it false gives . Choose true. Next, true gives , while false gives . Choose false. Finally true satisfies all clauses, giving weight ; choosing it false gives weight . Each chosen value preserves or increases the conditional expectation.
Worked example 6.1.6
(A tie between the two branches)
Take and , each of weight . Then and . Setting true gives , and setting it false gives : the branches tie, and either may be chosen. Take true. Then true gives , below , while false gives . Choose false. The final weight is , which exceeds the starting value and equals here. The branch with the smaller value is never chosen, which is exactly what keeps the value from falling.
Worked example 6.1.7
(Repeated clauses count separately)
Take twice, each copy of weight , and of weight . Then and . Setting true gives ; setting it false gives ; their average is , as the identity requires. Choose true. Then true gives and false gives . Choose false, for final weight .
Boundaries of the claim
Counterexample mode
Why two distinct variables matter
For the single clause , the probability of satisfaction is , not . It is a unit clause in disguise. The derivation above cannot be applied unchanged to instances containing unit clauses or repeated variables inside a clause. Negative weights also invalidate the comparison .
Common mistake
(Reading tightness in as tightness of the ratio )
The lower bound can be exact. Take the four unit-weight clauses , , and . Every assignment falsifies exactly one, so every assignment has value . Here , so this example shows tightness relative to ; it does not show a tight ratio relative to .
Common mistake
(Expecting an optimum, or a guarantee for longer clauses)
The result is a guarantee for this stated special case, not a statement about arbitrary clause sizes or a claim that the algorithm always finds an optimum. A single random assignment is guaranteed only in expectation; the deterministic guarantee comes from the conditional choices.
Summary
A uniform random assignment satisfies every two-variable clause with probability , hence weight in expectation. Fixing the variables one at a time and always keeping the branch with the larger conditional expectation never lowers that value, which gives a deterministic polynomial-time assignment of weight at least .
Exercises
Quick check
(For two distinct variables, compute the satisfaction probability of under independent fair assignment.)
Solution · Answer
Both literals are false only when is true and is false, an event of probability ; the answer is .
Quick check
(In the first worked example, explain why choosing false gives conditional value .)
Solution · Answer
The first clause contributes , the second contributes , and the third contributes ; their sum is .
Quick check
(A partial assignment has made both literals of a clause false. What is its contribution to ? What if the clause is already true?)
Solution · Answer
The contributions are respectively zero and the full clause weight, since later assignments cannot change either outcome.
Quick check
(Why does the four-clause example not prove that the ratio relative to is tight?)
Solution · Answer
Its optimum is and every assignment achieves , so its achieved ratio to the optimum is even though its value is .