Approximation algorithms for knapsack problems with cardinality constraints

Approximation algorithms for knapsack problems with cardinality constraints

0.00 Avg rating0 Votes
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: , , ,
Keywords: programming: dynamic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.