A Note on Approximation Schemes for Multidimensional Knapsack Problems
Published Online:1 May 1984https://doi.org/10.1287/moor.9.2.244
Abstract
Polynomial and fully polynomial approximation algorithms for single-dimensional knapsack problems have been extensively studied and a number of such algorithms constructed. This note shows that the problem of finding a fully polynomial approximation algorithm for multidimensional knapsack problems is NP-hard.
