TCS Journal 1976 Journal Article
Approximate algorithms for some generalized knapsack problems
- Ashok K. Chandra
- D.S. Hirschberg
- C.K. Wong
In this paper we construct approximate algorithms for the following problems: integer multiple-choice knapsack problem, binary multiple-choice knapsack problem and multi-dimensional knapsack problem. The main result can be described as follows: for every ε 0 one can construct a polynomial-time algorithm for each of the above problems such that the ratio of the value of the objective function by this algorithm and the optimal value is bounded below by 1 - ε.