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

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

0.00 Avg rating0 Votes
Article ID: iaor20043320
Country: Netherlands
Volume: 8
Issue: 1
Start Page Number: 5
End Page Number: 11
Publication Date: Mar 2004
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: programming: integer
Abstract:

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 kl+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(n2) 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.

Reviews

Required fields are marked *. Your email address will not be published.