New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

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.