The Library
Unbounded knapsack problems with arithmetic weight sequences
Tools
Deineko, Vladimir G. and Woeginger, Gerhard (2011) Unbounded knapsack problems with arithmetic weight sequences. European Journal of Operational Research, Vol.213 (No.2). pp. 384-387. doi:10.1016/j.ejor.2011.03.028 ISSN 0377-2217.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.ejor.2011.03.028
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(n(8)), 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. (C) 2011 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||
Library of Congress Subject Headings (LCSH): | Combinatorial optimization, Computational complexity, Dynamic programming, Polynomials | ||||
Journal or Publication Title: | European Journal of Operational Research | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0377-2217 | ||||
Official Date: | 1 September 2011 | ||||
Dates: |
|
||||
Volume: | Vol.213 | ||||
Number: | No.2 | ||||
Page Range: | pp. 384-387 | ||||
DOI: | 10.1016/j.ejor.2011.03.028 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | University of Warwick. Centre for Discrete Mathematics and Its Applications (DI-MAP), Engineering and Physical Sciences Research Council (EPSRC), Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Netherlands Organization for Scientific Research] (NWO) | ||||
Grant number: | EP/F017871 (EPSRC), 639.033.403 (NWO) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |