Key points are not available for this paper at this 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).
Ce Jin (Mon,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: