A new linear storage, polynomial-time approximation scheme for the subset-sum problem

Given a set of positive integers, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding, a given W. For this problem, we present a polynomial-time approximation scheme requiring only a linear storage, and prove that its worst-case performance dominates that of the linear-storage approximation schemes from the literature. A modification of the scheme requiring linear time and space for any fixed bound ε on the relative error, is also given. Extensive computational results on randomly generated test problems are reported. © 1990.