1
$\begingroup$

I'm sure this is a solved problem but I don't know what to search for:

I have a set of positive numbers (256 at the moment but it could get bigger) and I need to find another set of positive numbers such that for each number in the original set, there is a sub set of the new set that sums to within some error bound of the number:

  • Give $S\subset\mathbb{R}^+$
  • Find a small set $P\subset\mathbb{R}^+$
  • Sutch that $\forall i\in S, (\exists P_i\subset P,|i-\sum P_i|\le\epsilon)$

The best solution I have found so far is itterative:

  • find $M = max(S_n)$.
  • find $m = min(x | x \in S_n \wedge x > M/2)$
  • $P_{n+1} = P_n \cup m$
  • $S_{n+1} = (x | x \in S_n \wedge x < m) \cup (x - m | x \in S_n \wedge x \ge m)$
  • Stop when the approximation is good enough (i.e. $\forall x\in P_n,x\le\epsilon $)
  • 1
    By $\sum P_i = i \pm \epsilon$, you mean $\left|i - \sum P_i\right| \le \epsilon$, yes?2010-09-20
  • 0
    By "a small set $P$ contained in the positive reals" do you mean contained in $S$ or in $\mathbb{R}^+$? Also this is very much not set theory. Maybe combinatorics, I don't know.2010-09-20
  • 0
    @Rahul: yes, that is correct. You can edit that in if you want.2010-09-20
  • 0
    @Asaf: $\mathbb{R}^+$2010-09-20

1 Answers 1