A new fully polynomial approximation scheme for the knapsack problem. (English) Zbl 0908.90190
Jansen, Klaus (ed.) et al., Approximation algorithms for combinatorial optimization. International ICALP ’98 workshop, APPROX ’98, Aalborg, Denmark, July 18–19, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1444, 123-134 (1998).
Summary: A fully polynomial 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/\varepsilon^3)\) and \(O(n\cdot 1/\varepsilon)\) space, respectively. Our new approximation scheme requires only \(O(n+ 1/\varepsilon^2)\) space while also reducing the running time.
For the entire collection see [Zbl 0892.00051].
For the entire collection see [Zbl 0892.00051].
