A polynomial approximation scheme for the subset sum problem Original Research Article

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. We 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.