Approximate algorithms for some generalized knapsack problems |
| |
Authors: | Ashok K. Chandra D.S. Hirschberg C.K. Wong |
| |
Affiliation: | IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, U.S.A. |
| |
Abstract: | 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 - ε. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |