As we saw before, we must prove that for every instance of the problem the ratio between the algorithm solution and the optimal solution is bounded by a given value.
Actually, this is not easy to do in many cases. In some other cases this is duable. For instance, in the Christofides' algorithm for the metric version of tghe Traveling Salesman Problem, we bound the cost the Christofides' algorithm on instance I by the cost of the Minimum Spanning Tree on instance I plus the minimum cost matching of the odd vertices. The first value is a lower bound on the optimum, the second value is at least hal the optimum.
