Improved dynamic programming and approximation results for the knapsack problem with setups |
| |
| Authors: | Ulrich Pferschy Rosario Scatamacchia |
| |
| Affiliation: | 1. Department of Statistics and Operations Research, University of Graz, Graz, Austria;2. Dipartimento di Automatica e Informatica, Politecnico di Torino, Torino, Italy |
| |
| Abstract: | In this paper, we consider the 0–1 knapsack problem with setups. Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm that performs much better than a previous dynamic program and turns out to be also a valid alternative to an exact approach based on the use of an Integer Linear Programming (ILP) solver. Then we present a general inapproximability result. Furthermore, we investigate several relevant special cases that still permit fully polynomial‐time approximation schemes and others where the problem remains hard to approximate. |
| |
| Keywords: | 0– 1 knapsack problem with setups approximation scheme dynamic programming |
|
|
