Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

Hans Kellerer () and Ulrich Pferschy ()
Additional contact information
Hans Kellerer: University of Graz
Ulrich Pferschy: University of Graz

Journal of Combinatorial Optimization, 2004, vol. 8, issue 1, No 1, 5-11

Abstract: 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(n 2) 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 (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://link.springer.com/10.1023/B:JOCO.0000021934.29833.6b Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:8:y:2004:i:1:d:10.1023_b:joco.0000021934.29833.6b

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/B:JOCO.0000021934.29833.6b

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().