5 ms·
A Faster Pseudopolynomial Time Algorithm for Subset Sum (2015)
- ensconced 8y agoDoes this apply to the discrete Knapsack problem too?
- chaoxu 8y agoIt does not. For faster pseudopolynomial time algorithms to knapsack, see this https://arxiv.org/abs/1802.06440 https://arxiv.org/abs/1802.06440
- chaoxu 8y agoOne 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 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.