Tight bounds for periodicity theorems on the unbounded Knapsack problem

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.

► Developed three new periodicity bounds for UKP. ► Proved each new bound is tight. ► Showed two new bounds subsume known results.