## Max Sat

*Algorithm.*

Let y=<y_{1}, ... y_{n}> be any truth assignment for an instance I of Max Weighted Sat (i.e. each clause C has a positive weight w(C)) on variables x_{1},...,x_{n}. Let z=<z_{1}, ... z_{n}> b the complement of y, that is z_{i} is true if and only if y_{i} is false.

Compute the weight of the clauses satisfied by y and of those satisfied by z. Return the assignment that has largest weight.

*Question.*

Prove that the above algorithm achieves a 1/2-approximation