Article ID: | iaor2001909 |
Country: | Netherlands |
Volume: | 123 |
Issue: | 2 |
Start Page Number: | 333 |
End Page Number: | 345 |
Publication Date: | Jun 2000 |
Journal: | European Journal of Operational Research |
Authors: | Kellerer Hans, Pferschy Ulrich, Caprara Alberto, Pisinger David |
Keywords: | programming: dynamic |
We address a variant of the classical knapsack problem in which an upper bound is imposed on the number of items that can be selected. This problem arises in the solution of real-life cutting stock problems by column generation, and may be used to separate cover inequalities with small support within cutting-plane approaches to integer linear programs. We focus our attention on approximation algorithms for the problem, describing a linear-storage Polynomial Time Approximation Scheme (PTAS) and a dynamic-programming based Fully Polynomial Time Approximation Scheme (FPTAS). The main ideas contained in our PTAS are used to derive PTASs for the knapsack problem and its multi-dimensional generalization which improve on the previously proposed PTASs. We finally illustrate better PTASs and FPTASs for the subset sum case of the problem in which profits and weights coincide.