What are good approximation algorithms for the subset sum problem so far?

By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.

• FPTAS exist for knapsack. This is a special case. – singhsumit Mar 1 '12 at 20:20

Kellerer et al. (1997) gives with accuracy $\epsilon$ a $O(\min \{ n/ \epsilon, n + 1/ \epsilon^2 \log(1/ \epsilon) \})$ time and $O(n + 1/ \epsilon)$ space approximation scheme.

Further improving on this, Kellerer et al. (2003) gives a FPTAS with $O(\min \{n \cdot 1/ \epsilon , n + 1/ \epsilon^2 \log( 1/ \epsilon) \} )$ time and $O(n+1/ \epsilon)$ space. In addition, answering your question on "relatively fast running time", they noted that (based on computational results) that the scheme efficiently solves instances with up to $5000$ items with a guaranteed relative error smaller than $1/1000$.

I am unsure if there are any newer results. As noted, because subset sum is a special case of the knapsack problem, one will probably find even more results when searching for that.

UPDATE: You might also want to take a look at The Design of Approximation Algorithms, Williamson and Shmoys, 2011, see the chapter starting at page 65 about the Knapsack problem. They give a FPTAS (on page 68) for the Knapsack problem that runs in $O(n^3/\epsilon)$ time. It might be that the algorithms specifically designed for the Subset sum problem are faster than the more general ones for the Knapsack.

• $n$ is the number of integers to sum, right? – Juan Bermejo Vega Mar 4 '12 at 13:07
• @JuanBermejoVega Correct! – Juho Mar 4 '12 at 15:42

You question is very vague. Let's give it a try.

Let $$X_1,\ldots,X_n$$ be drawn ii from the uniform distribution on $$[-1,1]$$. For every $$\epsilon \ge e^{-n/(2C)}$$. With probability at least $$1-\exp(-(n/2-C\log(1/\epsilon))^2/(2n))$$ the following holds:

For ever $$x \in [-1/2,1/2]$$, there exists $$S \subseteq \{1,\ldots,n\}$$ such that $$|\sum_{i \in S}X_i - x| \le \epsilon$$.

This is Corollary 2.5 of Exponentially Small Bounds on the Expected Optimum of the Partition and Subset Sum Problems.