World's most popular travel blog for travel bloggers.

Subset Sum algorithm, why not split by 3+?

, , No Comments
Problem Detail: 

A classic algorithm for Subset Sum is to first split the input into two sets (A and B), evaluate the sums of the subsets of each, sort those sums for each A and B, then cleverly filter whole ranges of combinations by comparing the highest and lowest sums from each A and B.

Do we know (or does someone have an argument) why not to split the input into 3 or more sets rather than two?

I presume that there would be a combinatorial proof that doing so would either require the same or more number of steps.

Asked By : Tom
Answered By : Yuval Filmus

First of all, let me mention that the algorithm you mention is attributed to Horowitz and Sahni (1974), whose algorithm achieves time $O(2^{n/2})$ and space $O(2^{n/2})$. A major improvement due to Schroeppel and Shamir (1981) reduces memory consumption to $O(2^{n/4})$ while keeping the same running time; this algorithm divides the input into four sets.

The topic is of interest to cryptographers, and there has been a recent line of improvements: Howgrave-Graham and Joux (2010), Becker, Coron and Joux (2011), Dinur, Dunkelman, Keller and Shamir (2012) and Austrin, Kaski, Koivisto and Määttä (2013), which seems to be the latest word on the subject; the authors of the last paper are actually not cryptographers.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback