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

1

First, from your description, it appears that P=S is a valid, but likely non-optimal[1], solution.

Begin with this. Sort the set from smallest to largest. For every member of the set, if there exists a subset that sums to that member, remove that member. Do not repeat.

[1] For S=[1,2,4,8] then optimal P=[1,2,4,8]

  • 0
    That could work, but given that I'm dealing with real numbers, it's unlikely that it would be anywhere near ideal.2010-09-20
  • 0
    @BCS I don't see why this is any less applicable to reals2010-09-20
  • 0
    The probability that any of the value will be the sum of others is vanishingly small for reals. For integers of similar magnitude to the size, it is much more probable that will happen.2010-09-20
  • 0
    And a counter example: [1, 2, 3, 5, 8], $3+5=8$: remove 8, $2+3=5$: remove 5, $1+2=3$: remove 3. 5 and 8 can't be formed.2010-09-20
  • 0
    I took "approximation" to mean of the optimal solution, not an approximate solution. Sorry, some of the symbol notation here is unfamiliar to me. I corrected my answer to account for your counter-example.2010-09-21