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

We consider the bounded integer knapsack problem (BKP) $max{\Sigma }_{j=1}^n{p}_j{x}_j$, subject to: ${\Sigma }_{j=1}^n{w}_j{x}_j\le C$, and xj∈{0,1,…,mj}j=1,…,n. We use proximity results between the integer and the continuous versions to obtain an O(n³W²) algorithm for BKP, where W=maxj=1,…,nwj. The respective complexity of the unbounded case with mj=∞, for j=1,…,n, is O(n²W²). We use these results to obtain an improved strongly polynomial algorithm for the multicover problem with cyclical 1's and uniform right-hand side.