Tight bounds for periodicity theorems on the unbounded Knapsack problem

Tight bounds for periodicity theorems on the unbounded Knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor20118261
Volume: 215
Issue: 2
Start Page Number: 319
End Page Number: 324
Publication Date: Dec 2011
Journal: European Journal of Operational Research
Authors: , ,
Keywords: knapsack problem
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.

Reviews

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