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 ϵ-approximate algorithms. We present several ϵ-approximate Greedy Algorithms for the minimization version of the 0/1 Knapsack and the Subset-Sum Problem, that are also ϵ-approximate for the respective maximization version.