Tight bounds for periodicity theorems on the unbounded Knapsack problem
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Three new bounds for periodicity theorems on the unbounded Knapsack problem are developed. Periodicity theorems specify when it is optimal to pack one unit of the best item (the one with the highest profit-to-weight ratio). The successive applications of periodicity theorems can drastically reduce the size of the Knapsack problem under analysis, theoretical or empirical. We prove that each new bound is tight in the sense that no smaller bound exists under the given condition. 2011 Elsevier B.V. All rights reserved.