In this second lesson we will present more advanced applications of mathematical programming techniques for the design of approximation algorithms. In the first lesson we showed some basic examples of how mathematical programming techniques can be helpful in designing approximation algorithms. In particular, we showed an example of an application of linear programming relaxations and we also showed examples of an application of primal dual scheme, that is of algorithms that use the dual of a fractional relaxation of a linear program formulation as a guide to design approximation algorithms. In particular, we also discussed the fact that a fundamental aspect of designing similar algorithms is to provide a good rounding scheme. So, the first example we will see in this second part is that of designing an approximation algorithm for the max sat problem. In particular, the max weighted satisfiability problem. We will formulate this problem as an integer linear program, then relax the integrality constraints and finally we round the fractional solution to a feasible solution for the problem. Our main emphasis in this example is to show how randomization can be used in the rounded scheme. The ability of making probabilistic choices that are guided by the solution of the fractional relaxation may is in some cases a very useful tool to design better approximation algorithms. This is the first argument that we will treat in this second part. Since we have a randomized algorithm, we will have an expected value of the final solution where this expectation will be over all the random choices of the algorithms. In particular, we say that an algorithm A is rapproximate for a minimization problem if the expected solution given by the algorithm is at most r times the optimal solution. On the other hand, for a maximalization problem we will say that the algorithm is r approximate if the expected value of the algorithm is at least 1/r the optimal solution. And this should hold for every instance of the problem.

---