A well-solvable special case of the bounded knapsack problem

V.G. Deineko; G.J. Woeginger

doi:10.1016/j.orl.2011.01.006

A well-solvable special case of the bounded knapsack problem

V.G. Deineko
, G.J. Woeginger

Research output: Contribution to journal › Article › Academic › peer-review

10 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 language	English
Pages (from-to)	118-120
Number of pages	3
Journal	Operations Research Letters
Volume	39
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2011.01.006
Publication status	Published - 2011

Access to Document

10.1016/j.orl.2011.01.006

Cite this

@article{010d69435cc0440eae72b1e49880722e,

title = "A well-solvable special case of the bounded knapsack problem",

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{\textendash}16] for the unbounded knapsack problem.",

author = "V.G. Deineko and G.J. Woeginger",

year = "2011",

doi = "10.1016/j.orl.2011.01.006",

language = "English",

volume = "39",

pages = "118--120",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - A well-solvable special case of the bounded knapsack problem

AU - Deineko, V.G.

AU - Woeginger, G.J.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1016/j.orl.2011.01.006

DO - 10.1016/j.orl.2011.01.006

M3 - Article

SN - 0167-6377

VL - 39

SP - 118

EP - 120

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

A well-solvable special case of the bounded knapsack problem

Abstract

Access to Document

Fingerprint

Cite this