Fast Approximation Algorithms for Knapsack Problems

TLDR

The paper presents fully polynomial approximation schemes for knapsack problems. The algorithms build on Ibarra and Kim’s ideas, improving time and space by efficient scaling and a median‑finding routine that removes sorting. The schemes achieve near‑linear time and sub‑quadratic space: for 0‑1 knapsack, O(n log(1/ε)+1/ε⁴) time and O(n+1/ε³) space; for unbounded knapsack, O(n+1/ε³) time; for subset‑sum, O(n+1/ε³) time and O(n+1/ε²) space (or O(n+(1/ε²)log(1/ε)) time/space); for multiple‑choice, O(n log n+mn/ε) time and O(n+m²/ε) space.

Abstract

Fully polynomial approximation schemes for knapsack problems are presented. These algorithms are based on ideas of Ibarra and Kim, with modifications which yield better time and space bounds, and also tend to improve the practicality of the procedures. Among the principal improvements are the introduction of a more efficient method of scaling and the use of a median-finding routine to eliminate sorting. The 0-1 knapsack problem, for n items and accuracy ϵ > 0, is solved in (n log(1/ϵ) + 1/ϵ 4 ) time and O(n + 1/ϵ 3 ) space. The time bound is reduced to O(n + 1/ϵ 3 ) for the “unbounded” knapsack problem. For the “subset-sum” problem, O(n + 1/ϵ 3 ) time and O(n + 1/ϵ 2 ) space, or O(n + (1/ϵ 2 )log(1/ϵ)) time and space, are achieved. The “multiple choice” problem, with m equivalence classes, is solved in O(n log n + mn/ϵ) time and O(n + m 2 /ϵ) space.