Minimal Equivalent Binary Knapsack Inequalities
INFORMS Journal on Computing · 2011 · Volume 23 · Issue 3
Abstract
It is known that a knapsack inequality can be reduced to one having the same solutions but with “minimal” integer coefficients. Although this procedure is not practical because an exponential amount of work may be required to find such minimal equivalent knapsacks, knowledge of minimal equivalent knapsacks can reduce hard knapsacks to trivial ones, as we show for both Todd and Avis knapsacks. In this paper, we show that even with an oracle able to supply minimal equivalent knapsacks at no computational cost, their practical value may not materialize because there are minimal knapsack inequalities with exponential values.
Keywords
subset sum, hard knapsack problems, computational complexity
Enable JavaScript for citation tools and additional paper interactions.