The Library
Unbounded knapsack problems with arithmetic weight sequences
Tools
Tools
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. ISSN 0377-2217
Full text not available from this repository.
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 |
| Date: | 1 September 2011 |
| Volume: | Vol.213 |
| Number: | No.2 |
| Page Range: | pp. 384-387 |
| Identification Number: | 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) |
| References: | [1] F. Eisenbrand, S. Laue, A linear algorithm for integer programming in the plane, Mathematical Programming 102 (2005) 249–259. [2] D.D. Grant, On linear forms whose coefficients are in arithmetic progression, Israel Journal of Mathematics 15 (1973) 204–209. [3] D.S. Hirschberg, C.K. Wong, A polynomial-time algorithm for the knapsack problem with two variables, Journal of the ACM 23 (1976) 147–154. [4] H.W. Lenstra, Integer programming with a fixed number of variables, Mathematics of Operations Research 8 (1983) 538–548. [5] R.J. Lipton, Galactic Algorithms, 2010. <http://rjlipton.wordpress.com/2010/ 10/23/galactic-algorithms/> [6] G.S. Lueker, Two NP-complete problems in non-negative integer programming, Report No. 178, Computer Science Laboratory, Princeton University, 1975. [7] M. Magazine, G.L. Nemhauser, L.E. Trotter, When the greedy solution solves a class of knapsack problems, Operations Research 23 (1975) 207–217. [8] S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, Chichester, 1990. [9] K. Mathur, P. Venkateshan, A new lower bound for the linear knapsack problem with general integer variables, European Journal of Operational Research 178 (2007) 738–754. [10] J.L. Ramirez Alfonsin, On variations of the subset sum problem, Discrete Applied Mathematics 81 (1998) 1–7. [11] A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, 1986. [12] M. Zukerman, L. Jia, T. Neame, G.J. Woeginger, A polynomially solvable special case of the unbounded knapsack problem, Operations Research Letters 29 (2001) 13–16. |
| URI: | http://wrap.warwick.ac.uk/id/eprint/40035 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
