Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem

Approximate minimization algorithms for the 0/1 knapsack and subset-sum problem

0.00 Avg rating0 Votes
Article ID: iaor20052327
Country: Netherlands
Volume: 26
Issue: 2
Start Page Number: 55
End Page Number: 66
Publication Date: Mar 2000
Journal: Operations Research Letters
Authors: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.