Improved dynamic programming in connection with a fully polynomial time approximation scheme for the knapsack problem

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over l of the l-th entry of the first vector plus the sum of the first k−l+1 entries of the second vector. For this problem a new algorithm with O(nlogn) running time is presented thus improving upon the straightforward O(n²) time bound. The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme for the classical 0–1 knapsack problem by the same authors.