In this lecture we will present an overview of the main techniques that are used in the design of approximation algorithms based on mathematical programming techniques. Our idea is to exploit several techniques like linear programming, duality and semi-definitive programming to present better algorithms for several problems in combinatory optimisation.
Let us give some terminology:

• we will denote by P the problem we consider;
• we denote by I an instance of problem P;
• we define by S(I) the set of feasible solutions for instance I
• we have an objective function f ().
  

Moreover we have to distinguish if we like to maximise the objective function or if we like to minimise the objective function. If we deal with the minimisation problem, we have to select a feasible solution for every instance I of the problem in order to minimise the objective function. On the other hand, if we deal with maximisation problem, we have to select a feasible solution in order to maximise the objective function.