A Faster Pseudopolynomial Time Algorithm for Subset Sum (2015)

arxiv.org

31 pointspthyme3 comments

One of the authors here. Later we showed a much simpler algorithm for the O(u√n) running time. https://chaoxuprime.com/files/papers/subset-sum-simple.pdf

We have also prepared a journal version that combines those papers, and with some extra results. whomever interested can contact me.

Does this apply to the discrete Knapsack problem too?

It does not. For faster pseudopolynomial time algorithms to knapsack, see this https://arxiv.org/abs/1802.06440