Max Sat


Let y=<y1, ... yn> 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 x1,...,xn. Let z=<z1, ... zn> b the complement of y, that is zi is true if and only if yi is false.

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


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