New generic algorithms for hard knapsacks

摘要: In this paper, we study the complexity of solving hard knapsack problems, i.e., knapsacks with a density close to 1 where lattice-based low attacks are not an option. For such knapsacks, current state-of-the-art is 31-year old algorithm by Schroeppel and Shamir which based on birthday paradox techniques yields running time $\tilde{O}(2^{n/2})$ for n elements uses $\tilde{O}(2^{n/4})$ storage. We propose here two new algorithms improve bound, finally lowering down either $\tilde{O} (2^{0.385\, n})$ or (2^{0.3113\, under reasonable heuristic. also demonstrate practicality these implementation.