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

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.

authors

• Lawley, Mark

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

publisher

• Elsevier  Publisher

published in

• European Journal of Operational Research  Journal

Digital Object Identifier (DOI)

• 10.1016/j.ejor.2011.06.010

start page

• 319

end page

• 324

volume

• 215

issue

• 2

URL

• http://dx.doi.org/10.1016/j.ejor.2011.06.010