| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652760 | Electronic Notes in Discrete Mathematics | 2010 | 8 Pages |
In this paper, we study the sensitivity of the optimum of the single knapsack problem (KP) and the knapsack sharing problem (KSP) to perturbations of the weight of a subset of items. We try to establish lower and upper bounds limits when a dynamic programming is applied. First, we show how to stabilize an optimal solution of KP, by considering two cases. A first case in which all perturbations are negative or nonnegative. A second case – that is a general case – for which a set of the perturbed items is divided into two disjoints subsets: a subset containing the items with nonnegative perturbations and another subset composed of items with negative perturbations. Second and last, we show how we can adapt the results established for KP to the KSP.
