Our strategy
will be as follows. We first compute an optimal solution of the relaxed
problem. We call this optimal solution x*. LB(I), that is the optimal solution of the relaxed problem on instance I is given by g(x*), that is the minimum of function g(x). Then we need to produce a solution that is feasible for the original problem. Why? Because the optimal solution for the relaxed problem may be unfeasible for the original problem. What we have to do now is what it is called the rounding process. In doing that we want to loose a factor that is as small as possible because this factor will give the performance guarantee of our algorithm. In particular in the rounding from x* to x, if we can say that the solution produced by our algorithm on instance I is at most r times the value of the optimal solution of the relaxed problem, then we have an r-approximation of the original problem. | ![]() |