Often in approximations you can prove an upper bound on the optimal solution, even if you don't know the optimal solution itself. An easy example is by using d

Often in approximations you can prove an upper bound on the optimal solution, even if you don't know the optimal solution itself. An easy example is by using duality when solving linear programs. And sometimes your upper bound is close enough to what you already have so you can just say something like "well my solution gets 190 points, I have an upper bound of 190.5 points, and all point rewards are integral so I must have the optimal solution."