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}^+$
  • Such 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 iterative:

  • 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 $)
  • 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
    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