Fast Approximation Algorithms for Knapsack Problems
Eugene L. Lawler
Source 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.