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 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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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