Now we want to go further and show a further example of application of linear programming techniques and of the relationship between the primal and dual of a problem to the design of approximation algorithm. In particular, we will show two algorithms. The first algorithm for the multi-cut problem. The multi-cut problem is strictly related to the multi-commodity flow problem. And, as a second problem we will present an approximation algorithm for the multi-commodity flow problems without using linear programming techniques.

---