Unbounded knapsack problems with arithmetic weight sequences

V.G. Deineko; G.J. Woeginger

doi:10.1016/j.ejor.2011.03.028

Unbounded knapsack problems with arithmetic weight sequences

V.G. Deineko, G.J. Woeginger

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

3 Citations (Scopus)

Abstract

We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n8), where n denotes the number of distinct items in the instance. Furthermore, we extend our approach to a slightly more general class of knapsack instances.

Original language	English
Pages (from-to)	384-387
Journal	European Journal of Operational Research
Volume	213
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2011.03.028
Publication status	Published - 2011

Access to Document

10.1016/j.ejor.2011.03.028

Cite this

@article{995e57f88a0647a28096b85d4e863bd1,

title = "Unbounded knapsack problems with arithmetic weight sequences",

abstract = "We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n8), where n denotes the number of distinct items in the instance. Furthermore, we extend our approach to a slightly more general class of knapsack instances.",

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

year = "2011",

doi = "10.1016/j.ejor.2011.03.028",

language = "English",

volume = "213",

pages = "384--387",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Unbounded knapsack problems with arithmetic weight sequences

AU - Deineko, V.G.

AU - Woeginger, G.J.

PY - 2011

Y1 - 2011

N2 - We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n8), where n denotes the number of distinct items in the instance. Furthermore, we extend our approach to a slightly more general class of knapsack instances.

AB - We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n8), where n denotes the number of distinct items in the instance. Furthermore, we extend our approach to a slightly more general class of knapsack instances.

U2 - 10.1016/j.ejor.2011.03.028

DO - 10.1016/j.ejor.2011.03.028

M3 - Article

SN - 0377-2217

VL - 213

SP - 384

EP - 387

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

Unbounded knapsack problems with arithmetic weight sequences

Abstract

Access to Document

Fingerprint

Cite this