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.