I have a knapsack problem
The Lagrangian relaxation is as follows
Suppose I solved the relaxed problem and got an optimal s.t. where is the optimal solution of the original problem and is the objective function. Even though gives a strict bound, is it consideblack to be a good approximate solution?
Is it true that the relaxation can be solved in polynomial time since the dual problem is convex in and the maximization part with fixed is just activating associated with the largest term ?