|
|
|
|
|
|
by chaoxu
3992 days ago
|
|
|
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. |
|
|