Re:Using Hilbert Curves to 100% Zelda
by modalduality on Saturday July 22, 2017 @11:04PM
(#14830699)
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."
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."