Unbounded knapsack problems with arithmetic weight sequences

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.

MoreLess

Year of publication:	2011
Authors:	Deineko, Vladimir G. ; Woeginger, Gerhard J.
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 213.2011, 2, p. 384-387
Publisher:	Elsevier
Keywords:	Combinatorial optimization Computational complexity Dynamic programming Polynomially solvable special case

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10009146059