| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143390 | Operations Research Letters | 2009 | 4 Pages |
Abstract
We consider the bounded integer knapsack problem (BKP) max∑j=1npjxj, subject to: ∑j=1nwjxj≤C, and xj∈{0,1,…,mj},j=1,…,nxj∈{0,1,…,mj},j=1,…,n. We use proximity results between the integer and the continuous versions to obtain an O(n3W2)O(n3W2) algorithm for BKP, where W=maxj=1,…,nwjW=maxj=1,…,nwj. The respective complexity of the unbounded case with mj=∞mj=∞, for j=1,…,nj=1,…,n, is O(n2W2)O(n2W2). We use these results to obtain an improved strongly polynomial algorithm for the multicover problem with cyclical 1’s and uniform right-hand side.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Arie Tamir,