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.
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 |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Hardness of approximation of the discrete time-cost tradeoff problem
Deineko, Vladimir G., (2001)
-
A solvable case of the quadratic assignment problem
Deineko, Vladimir G., (1997)
-
Erratum: The Travelling Salesman and the PQ-Tree
Burkard, Rainer E., (1999)
- More ...