A Faster Pseudopolynomial Time Algorithm for Subset Sum (2015) (opens in new tab)

(arxiv.org)

31 pointspthyme7y ago3 comments

3 comments

3 comments · 2 top-level

ensconced7y ago· 1 in thread

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

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.

j / k navigate · click thread line to collapse