HNGlance

Top Best New Show

A Faster Pseudopolynomial Time Algorithm for Subset Sum

http://arxiv.org/abs/1507.02318

by chaoxu • 11 years ago

34 2 11 years ago

AR

Related Stories

Loading related stories...

Comments

2

dhruvbird• 11 years ago

Any simple explanation for this? I'm interested in learning more about it.

chaoxu• 11 years 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.

Source preview

arxiv.org

HNGlance

© 2024-2026 HN Glance. Story content belongs to its original sources.

Privacy
Terms