Fast Approximation Algorithms for Knapsack Problems

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.