Approximate minimization algorithms for the 0/1 Knapsack and Subset-Sum Problem

摘要

The well-studied 0/1 Knapsack and Subset-Sum Problem are maximization problems that have an equivalent minimization version. While exact algorithms for one of these two versions also yield an exact solution for the other version, this does not apply to epsilon-approximate algorithms. We present several epsilon-approximate Greedy Algorithms for the minimization version of the 0/1 Knapsack and the Subset-Sum Problem, that are also epsilon-approximate for the respective maximization version. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 3]