Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem |
| |
Authors: | Hans Kellerer Ulrich Pferschy |
| |
Affiliation: | (1) Department of Statistics and Operations Research, University of Graz, Universitätsstr. 15, A-8010 Graz, Austria |
| |
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 of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) 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 (FPTAS) for the classical 0–1 knapsack problem by the same authors. |
| |
Keywords: | dynamic programming knapsack problem fully polynomial approximation scheme |
本文献已被 SpringerLink 等数据库收录! |