Reoptimizing the 0–1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on nn items is known and a very small number kk of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+kn+k items, given an optimal solution on the nn items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an αα-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of 12−α, which is always greater than αα, and therefore that this algorithm always outperforms the corresponding αα-approximation algorithm applied from scratch on the n+kn+k items. We show that this bound is tight when the classical Ext-Greedy   algorithm and the G34 algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.