ISSN:
1573-2886
Keywords:
knapsack problem
;
fully polynomial approximation scheme
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A fully polynomial time approximation scheme (FPTAS) is presented for the classical 0-1 knapsack problem. The new approach considerably improves the necessary space requirements. The two best previously known approaches need O(n + 1/ε3) and O(n · 1/ε) space, respectively. Our new approximation scheme requires only O(n + 1/ε2) space while also reducing the running time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009813105532
Permalink