Course full name
Advanced Techniques for Combinatorial Algorithms
Course ID number
1920-87R-04
Max Sat
Completion requirements
Opened: Thursday, 28 May 2020, 12:00 AM
Algorithm.
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.
Question.
Prove that the above algorithm achieves a 1/2-approximation