Resumen
We consider the bounded integer knapsack problem (BKP) , subject to: , and xj{0,1,…,mj},j=1,…,n. We use proximity results between the integer and the continuous versions to obtain an O(n3W2) algorithm for BKP, where W=maxj=1,…,nwj. The respective complexity of the unbounded case with mj=∞, for j=1,…,n, is 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.
In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of NP-completeness is incorrect, and instead we give a sufficient condition of membership of NP. We also provide a pseudo-polynomial algorithm for a special case.