A Fast Approximation Algorithm for the Subset-sum Problem

The subset-sum problem (SSP) is defined as follows: given a positive integer bound and a set of n positive integers find a subset whose sum is closest to, but not greater than, the bound. We present a randomized approximation algorithm for this problem with linear space complexity and time complexity of O( n log n ). Experiments with random uniformly-distributed instances of SSP show that our algorithm outperforms, both in running time and average error, Martello and Toth's (1984) quadratic greedy search, whose time complexity is O( n ²). We propose conjectures on the expected error of our algorithm for uniformly-distributed instances of SSP and provide some analytical arguments justifying these conjectures. We present also results of numerous tests.