A polynomial approximation scheme for the subset sum problem

The subset sum problem is defined as: given a set of n+1 positive integers, a1,a2,...,an and b, find a subset of the ai’s such that their sum is the closest to b without exceeding the value b. The authors propose a variation of the well-known polynomial approximation scheme of Martello and Toth for this problem. From a practical point of view the suggested algorithm has a better experimental error behaviour and comparable running time. It is also shown that in the worst theoretical case both algorithms yield the same error.