# A Fast Approximation Algorithm for the Subset-Sum Problem

## Bartosz Przydatek

```
```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 [MartelloToth'84] quadratic greedy search,
whose time complexity is $O(n^2)$.

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.