# Information Security and Cryptography Research Group

## A Fast Approximation Algorithm for the Subset-Sum Problem

### Bartosz Przydatek

International Transactions in Operational Research, Blackwell Publishers, vol. 9, no. 4, pp. 437–459, Aug 2002, A preliminary version of this paper was presented at IFORS '99, 15th Triennial Conference of IFORS.

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.

## BibTeX Citation

@article{Przyda02,
author       = {Bartosz Przydatek},
title        = {A Fast Approximation Algorithm for the Subset-Sum Problem},
journal      = {International Transactions in Operational Research},
pages        = 437--459,
number       = 4,
volume       = 9,
year         = 2002,
month        = 8,
note         = {A preliminary version of this paper was presented at IFORS~'99, 15th Triennial Conference of IFORS},
publisher    = {Blackwell Publishers},
}