Let us consider the subset sum problem with $S = S_i = \{1,2,..,i\}$. There are of course $2^{|S|}$ different sums that can be formed.

Now it seems that though the sums are not in order and thus not searchable efficiently there is some structure as indicated by the picture below. In the image there are the cases i = 1..7. The "boxes" in bold indicate runs of increasing numbers, that is increasing values of sums, while the row numbers indicate how many numbers the sums consist of. Now it appears that the minimums (and maximums) of these boxes are in order. Now, to me it seems one could exploit this structure to make a search in $O(|S|^3)$ -time. That is, pick a number in a box, then iterate below and above to find the min and max of the box. This is $\Theta(|S|)$. If the max is less than the target, then pick some box to the right of the current one. If the min is greater than the target, then pick some box to the left of the current one. The maximum size of a box is exactly |S|. There are |S|+1 rows to consider (to perform a binary search on). Thus the running time is $O(|S|^3)$, even though the number of boxes is $2^{|S|-2}+2$.

Subset sum structure.

An example of the contents of boxes is the case of i=4, where the box structure is |0|;|1 2 3|4|;|345|567|;|6|789|;|10|;, where the rows are separated by semicolons. Here the |567| box is the |123| box (1-row) of the i=3 case with 4 added to each sum. And the |345| box is the box from the 2-row in the i=3 case. The key property is that the min's and max's are in order (in this case). So: 5 >= 3 and 7 >= 5. So, if looking for 6, one could conclude that it must be in the box other than |345|, if it exists at all. Maybe not so good an example as there are only two boxes.

A more illustrative example, perhaps:

S = {x1}
0: 0
1: x1

S = {x1, x2}, x1 <= x2
0: 0
1: x1 <= x2
2: x1+x2

S = {x1, x2, x3}, x1 <= x2 <= x3
0: 0
1: x1 <= x2 <= x3
2: x1+x2 <= x1+x3 <= x2+x3
3: x1+x2+x3

S = {x1,x2,x3,x4}, x1 <= x2 <= x3 <= x4
0: 0
1: x1 x2 x3 x4
2: x1+x2 <= x1+x3 <= x2+x3 ? x1+x4 <= x2+x4 <= x3+x4
3: x1+x2+x3 <= x1+x2+x4 <= x1+x3+x4 <= x2+x3+x4
4: x1+x2+x3+x4

S = {x1,x2,x3,x4, x5}, x1 <= x2 <= x3 <= x4 <= x5
0: 0
1: x1 x2 x3 x4 x5
2: x1+x2 <= x1+x3 <= x2+x3 ? x1+x4 <= x2+x4 <= x3+x4 ? x1+x5 <= x2+x5 <= x3+x5 <= x4+x5
3: x1+x2+x3 <= x1+x2+x4 <= x1+x3+x4 <= x2+x3+x4 ? x1+x2+x5 <= x1+x3+x5 <= x2+x3+x5 ? x1+x4+x5 <= x2+x4+x5 <= x3+x4+x5
4: x1+x2+x3+x4 <= x1+x2+x3+x5 <= x1+x2+x4+x5 <= x1+x3+x4+x5 <= x2+x3+x4+x5
5: x1+x2+x3+x4+x5

And so on... One can add as many xi's as one wishes.
The question mark indicates a box boundary, where one doesn't know the order of x2+x3 and x1+x4 unless they are fixed to some values.
But what is known is that eg. for the |S|=4 case: x1+x2 <= x1+x4 and x2+x3 <= x3+x4, allowing one to find the right box.

The question is: did I miss something obvious in the analysis? Can this be generalized to some other kind of sets?

edit: Actually, it looks like what is found is a range of boxes instead of a single box. I mean, what prevents the target to fit between the min and max of every box other than the first and the last on a row, say?

So the updated question is: Is there a sub-exponential upper bound on the number of boxes to search?

  • $\begingroup$ Try to prove that this algorithm always works. $\endgroup$ – Yuval Filmus Oct 26 '15 at 10:58
  • $\begingroup$ I think that is the next step, yes. For what it's worth it depends on whether the property of min's and max's being in order holds. $\endgroup$ – user72935 Oct 26 '15 at 11:13
  • 1
    $\begingroup$ Either it always works or it doesn't. If it doesn't always work, try to describe a large class of instances on which it does work. $\endgroup$ – Yuval Filmus Oct 26 '15 at 11:17
  • $\begingroup$ See mathoverflow.net/questions/39386/… $\endgroup$ – Craig Feinstein Oct 27 '15 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.