<p>You question is very vague. Let's give it a try.</p>

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

<blockquote>
  <p>For ever <span class="math-container">$x \in [-1/2,1/2]$</span>, there exists <span class="math-container">$S \subseteq \{1,\ldots,n\}$</span> such that <span class="math-container">$|\sum_{i \in S}X_i - x| \le \epsilon$</span>. </p>
</blockquote>

<p>This is Corollary 2.5 of <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.6115&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Exponentially Small Bounds on the Expected Optimum
of the Partition and Subset Sum Problems</a>.</p>

CC BY-SA 4.0
2020-06-16T18:18:42.157Z
2020-06-16T18:18:42.157Z
dohmatob
<p><a href="http://www.springerlink.com/content/p0p1x17217217r29/">Kellerer et al. (1997)</a> 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.</p>

<p>Further improving on this, <a href="http://www.sciencedirect.com/science/article/pii/S0022000003000060">Kellerer et al. (2003)</a> 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$.</p>

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

<p>UPDATE: You might also want to take a look at <a href="http://www.designofapproxalgs.com/download.php">The Design of Approximation Algorithms, Williamson and Shmoys, 2011</a>, 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.</p>

CC BY-SA 3.0
2012-03-04T13:07:48.430Z
$n$ is the number of integers to sum, right?
Juan Bermejo Vega
CC BY-SA 3.0
2012-03-04T15:42:17.470Z
@JuanBermejoVega Correct!
Juho
CC BY-SA 3.0
2012-03-01T22:59:45.390Z
2012-03-03T00:37:43.000Z
2012-03-03T00:37:43.000Z
Juho
<p>By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.</p>

CC BY-SA 3.0
2012-03-01T20:20:28.843Z
FPTAS exist for knapsack. This is a special case.
singhsumit
<ds.algorithms><np-hardness><approximation-algorithms><approximation-hardness><subset-sum>
What are good approximation algorithms for the subset sum problem so far?
sma
# What are good approximation algorithms for the subset sum problem so far?

(Asked by: username_0 on 2012-03-01)

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

**Tags:** ds.algorithms, np-hardness, approximation-algorithms, approximation-hardness, subset-sum

> **Comments:**
> **username_1**: FPTAS exist for knapsack. This is a special case.  

---

## 2 answers

### Answer by username_3 on 2012-03-01. Score: 14 | Accepted answer

[Kellerer et al. (1997)](http://www.springerlink.com/content/p0p1x17217217r29/) 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)](http://www.sciencedirect.com/science/article/pii/S0022000003000060) 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 username_0ller 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](http://www.designofapproxalgs.com/download.php), 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.

> **Comments:**
> **username_4**: $n$ is the number of integers to sum, right?  
> **username_3**: @JuanBermejoVega Correct!  

---

### Answer by username_2 on 2020-06-16. Score: 0

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.6115&rep=rep1&type=pdf).


---

