A well-solvable special case of the bounded knapsack problem

作者：Deineko Vladimir G; Woeginger Gerhard J^*

来源：Operations Research Letters, 2011, 39(2): 118-120.

DOI：10.1016/j.orl.2011.01.006

• Combinatorial optimization
• Computational complexity
• Polynomial time algorithm
• Cross ratio ordered

We identify a polynomially solvable special case of the bounded knapsack problem that is characterized by a set of simple inequalities relating item weight ratios to item profit ratios. Our result generalizes and extends a corresponding result of Zukerman, et al. [M. Zukerman, L. Jia, T. Neame, G.J. Woeginger, A polynomially solvable special case of the unbounded knapsack problem, Operations Research Letters 29 (2001) 13-16] for the unbounded knapsack problem.

• 出版日期2011-3