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: | Jungnickel Dieter, Gntzer Michael M. |
Keywords: | heuristics |
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.