A Faster Pseudopolynomial Time Algorithm for Subset Sum (2015) (arxiv.org) 31 points by pthyme 7y ago ↗ HN
[–] ensconced 7y ago ↗ Does this apply to the discrete Knapsack problem too? [–] chaoxu 7y ago ↗ It does not. For faster pseudopolynomial time algorithms to knapsack, see this https://arxiv.org/abs/1802.06440
[–] chaoxu 7y ago ↗ It does not. For faster pseudopolynomial time algorithms to knapsack, see this https://arxiv.org/abs/1802.06440
[–] chaoxu 7y ago ↗ 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.pdfWe have also prepared a journal version that combines those papers, and with some extra results. whomever interested can contact me.
3 comments
[ 2.6 ms ] story [ 18.5 ms ] threadWe have also prepared a journal version that combines those papers, and with some extra results. whomever interested can contact me.