| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 476998 | European Journal of Operational Research | 2011 | 4 Pages |
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.
► The paper solves a natural special case of the knapsack problem. ► The paper unifies several ideas and methods from the area. ► The paper uses an IP-formulation in a novel way.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Vladimir G. Deineko, Gerhard J. Woeginger,