A POLYNOMIAL-APPROXIMATION SCHEME FOR THE SUBSET SUM PROBLEM

The subset sum problem is defined as: given a set of n + 1 positive in tegers, a1, a2, ..., a(n) and b, find a subset of the a(i)'s such that their sum is the closest to b without exceeding the value b. We propo se a variation of the well-known polynomial approximation scheme of Ma rtello and Toth for this problem. From a practical point of view the s uggested algorithm has a better experimental error behaviour and compa rable running time. It is also shown that in the worst theoretical cas e both algorithms yield the same error.