Retour aux résultats
Articles (2010), Discrete Applied Mathematics, 158 (17), pp. 1879-1887

Reoptimizing the 0–1 knapsack problem

ARCHETTI Claudia , Bertazzi Luca, Speranza M. Grazia

In this paper we study the problem where an optimal solution of a knapsack problem on items is known and a very small number of new items arrive. The objective is to find an optimal solution of the knapsack problem with items, given an optimal solution on the items (reoptimization of the knapsack problem). We show that this problem, even in the case , 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 , which is always greater than , and therefore that this algorithm always outperforms the corresponding -approximation algorithm applied from scratch on the items. We show that this bound is tight when the classical Ext-Greedy algorithm and the 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. Lien vers l'article

ARCHETTI, C., BERTAZZI, L. and SPERANZA, M.G. (2010). Reoptimizing the 0–1 knapsack problem. Discrete Applied Mathematics, 158(17), pp. 1879-1887.

Mots clés : #0–1-knapsack-problem, #Reoptimization, #Worst, #case-analysis