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

  • 8
    $\begingroup$ FPTAS exist for knapsack. This is a special case. $\endgroup$
    – singhsumit
    Commented Mar 1, 2012 at 20:20

2 Answers 2


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.

  • $\begingroup$ $n$ is the number of integers to sum, right? $\endgroup$ Commented Mar 4, 2012 at 13:07
  • $\begingroup$ @JuanBermejoVega Correct! $\endgroup$
    – Juho
    Commented Mar 4, 2012 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.