0-1 Knapsack in Nearly Quadratic Time

We study pseudo-polynomial time algorithms for the fundamental 0-1 Knapsack problem. Recent research interest has focused on its fine-grained complexity with respect to the number of items n and the maximum item weight wmax. Under (min,+)-convolution hypothesis, 0-1 Knapsack does not have O((n+wmax)2−δ) time algorithms (Cygan-Mucha-Węgrzycki-Włodarczyk 2017 and K'unnemann-Paturi-Schneider 2017). On the upper bound side, currently the fastest algorithm runs in Õ(n + 12/5) time (Chen, Lian, Mao, and Zhang 2023), improving the earlier O(n + wmax3)-time algorithm by Polak, Rohwedder, and Węgrzycki (2021).