A Faster Pseudopolynomial Time Algorithm for Subset Sum(arxiv.org)
arxiv.org
A Faster Pseudopolynomial Time Algorithm for Subset Sum
http://arxiv.org/abs/1507.02318
1 comments
Any simple explanation for this? I'm interested in learning more about it.
Author here.
The idea is a mix of many things. This is not how we write it in the paper, but just for intuition.
If Σ(S) is the set of all subset sums of S, where S={s_1,...,s_n}, then
Σ(S) = Σ(s_1)+Σ(s_2)+...+Σ(s_n).
Here A+B = {a+b|a in A, b in B} + is associative and commutative. Now we want to add parenthesis on that formula in a way such that it is fast. Similar to matrix chain multiplication. We make sure + can be fast if certain property are satisfied(Theorem 2), and the rest is just figuring out the right way to add parenthesis.
If Σ(S) is the set of all subset sums of S, where S={s_1,...,s_n}, then
Σ(S) = Σ(s_1)+Σ(s_2)+...+Σ(s_n).
Here A+B = {a+b|a in A, b in B} + is associative and commutative. Now we want to add parenthesis on that formula in a way such that it is fast. Similar to matrix chain multiplication. We make sure + can be fast if certain property are satisfied(Theorem 2), and the rest is just figuring out the right way to add parenthesis.