Name
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 - ε. |
Year | DOI | Venue |
|---|---|---|
1976 | 10.1016/0304-3975(76)90048-7 | Theor. Comput. Sci. |
DocType | Volume | Issue |
Journal | 3 | 3 |
ISSN | Citations | PageRank |
Theoretical Computer Science | 41 | 4.19 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashok K. Chandra | 1 | 3116 | 1215.02 |
| D. S. Hirschberg | 2 | 1265 | 506.25 |
| C. K. Wong | 3 | 1459 | 513.44 |