A Fast Approximation Algorithm For The Subset-Sum Problem

The subset-sum problem (SSP) is de ned as follows: given a positive integer bound and a set of n positive integers nd 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 uniformlydistributed instances of SSP show that our algorithm outperforms, both in running time and average error, Martello & Toth's (1984) quadratic greedy search, whose time complexity is O(n²). We propos