Simple and Faster Algorithms for Knapsack

In this paper, we obtain a number of new simple pseudo-polynomial time algorithms on the well-known knapsack problem, focusing on the running time dependency on the number of items $n$, the maximum item weight $w_{\mathrm{m}\mathrm{a}\mathrm{x}}$, and the maximum item profit $p_{\mathrm{m}\mathrm{a}\mathrm{x}}$. Our results include: - An $\tilde{O}(n^{3\mathrm{/}2}\cdot \min \{w_{\mathrm{m}\mathrm{a}\mathrm{x}},p_{\mathrm{m}\mathrm{a}\mathrm{x}}\})$-time randomized algorithm for 0-1 knapsack, improving the previous $\tilde{O}(\min \{n{w}_{\mathrm{m}\mathrm{a}\mathrm{x}}{p}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2\mathrm{/}3},n{p}_{\mathrm{m}\mathrm{a}\mathrm{x}}{w}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2\mathrm{/}3}\})$ [Bringmann and Cassis, ESA’23] for the small $n$ case. - An $\tilde{O}(n+\min \{w_{\mathrm{m}\mathrm{a}\mathrm{x}},p_{\mathrm{m}\mathrm{a}\mathrm{x}}{\}}^{5\mathrm{/}2})$-time randomized algorithm for bounded knapsack, improving the previous $O(n+\min \{w_{\mathrm{m}\mathrm{a}\mathrm{x}}^3,p_{\mathrm{m}\mathrm{a}\mathrm{x}}^3\})$ [Polak, Rohwedder and Wegrzyck, ICALP’21].