A well-solvable special case of the bounded knapsack problem

V.G. Deineko, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
3 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)118-120
Number of pages3
JournalOperations Research Letters
Volume39
Issue number2
DOIs
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'A well-solvable special case of the bounded knapsack problem'. Together they form a unique fingerprint.

Cite this