COMS 482: unofficial class blog

In the previous lecture we showed an approximation to the Knapsack algorithm that is fast when v^* = max v_i is small. So, convert a knapsack problem into one where v^* is small by choosing b and converting v_i -> ceil(v_i/b). We want an answer within (1 + e) of the true value, so b = (e/n) * v^*.