Using LP duality as a lower bound on the optimal solution is a very powerful way of designing approximation algorithms. What we describe is a general scheme of designing algorithms that are based on the use of duality. We write a linear programming formulation for the original problem, then we relax the integrality constraints, then we write the dual to the relaxed formulation. We maintain a solution that is feasible for the dual, meanwhile we construct a solution for the primal that is approaching feasibility and we stop when the solution has really reached feasibility. The use of duality is very important for the analysis. We do not need to solve the dual problem. We just use the dual problem for the analysis of the algorithm.

---