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

Question

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

Answer 1

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.

Answer 2

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.