Consider the MAX-SAT problem, see https://en.wikipedia.org/wiki/Maximum satisfiability-problem. (a) Given an integer linear programming formulation of MAX-SAT Hint: There should be two types of variables in the linear program: One linear programming variable r, for each variable v in the MAX-SAT instance, and one linear programming variable ye for cach clause c in the MAX-SAT instance. (b) Let a, be an optimal solution to the relaxed (rational) linear program. Show that setting the variable v to 1 with probability r, and to 0 otherwise (independent of the setting of the other variables) yields a (1-1-approxmation in expectation Hint: Use the fact that the geometric mean is at most the arithmetic mean https: //en.wikipedia.org/wiki/Inequality_of_arithmetic_ and_geometric_means Also use the fact that if f(x) is a concave function on an interval [a, b], you can lower bound f(z) in this interval the line that passes through (a, f(a)) and e setting of the other variables) vields a Consider the MAX-SAT problem, see https://en.wikipedia.org/wiki/Maximum satisfiability-problem. (a) Given an integer linear programming formulation of MAX-SAT Hint: There should be two types of variables in the linear program: One linear programming variable r, for each variable v in the MAX-SAT instance, and one linear programming variable ye for cach clause c in the MAX-SAT instance. (b) Let a, be an optimal solution to the relaxed (rational) linear program. Show that setting the variable v to 1 with probability r, and to 0 otherwise (independent of the setting of the other variables) yields a (1-1-approxmation in expectation Hint: Use the fact that the geometric mean is at most the arithmetic mean https: //en.wikipedia.org/wiki/Inequality_of_arithmetic_ and_geometric_means Also use the fact that if f(x) is a concave function on an interval [a, b], you can lower bound f(z) in this interval the line that passes through (a, f(a)) and e setting of the other variables) vields a