Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $)
share|improve this question
1  
By $\sum P_i = i \pm \epsilon$, you mean $\left|i - \sum P_i\right| \le \epsilon$, yes? –  Rahul Sep 20 '10 at 5:30
    
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. –  Asaf Karagila Sep 20 '10 at 7:46
    
@Rahul: yes, that is correct. You can edit that in if you want. –  BCS Sep 20 '10 at 14:50
    
@Asaf: $\mathbb{R}^+$ –  BCS Sep 20 '10 at 14:53
add comment

1 Answer

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]

share|improve this answer
    
That could work, but given that I'm dealing with real numbers, it's unlikely that it would be anywhere near ideal. –  BCS Sep 20 '10 at 3:12
    
@BCS I don't see why this is any less applicable to reals –  Sparr Sep 20 '10 at 5:23
    
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. –  BCS Sep 20 '10 at 14:56
    
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. –  BCS Sep 20 '10 at 14:59
    
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. –  Sparr Sep 21 '10 at 4:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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