Publication
Theoretical Computer Science
Paper

Approximate algorithms for some generalized knapsack problems

View publication

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 - ε. © 1976.

Date

Publication

Theoretical Computer Science

Authors

Topics

Share