Tight bounds for periodicity theorems on the unbounded Knapsack problem Academic Article uri icon

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.

published proceedings

  • European Journal of Operational Research

author list (cited authors)

  • Huang, P. H., Lawley, M., & Morin, T.

citation count

  • 7

complete list of authors

  • Huang, Ping H||Lawley, Mark||Morin, Thomas

publication date

  • December 2011