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{ max}$, and the maximum item profit $p_\mathrm{ max}$. Our results include: - An $\widetilde{ O}(n^{ 3/2}\cdot \min\{ w_\mathrm{ max},p_\mathrm{ max}\})$-time randomized algorithm for 0-1 knapsack, improving the previous $\widetilde{ O}(\min\{ n w_\mathrm{ max} p_\mathrm{ max}^{ 2/3},n p_\mathrm{ max} w_\mathrm{ max}^{ 2/3}\})$ [Bringmann and Cassis, ESA'23] for the small $n$ case. - An $\widetilde{ O}(n+\min\{ w_\mathrm{ max},p_\mathrm{ max}\}^{ 5/2})$-time randomized algorithm for bounded knapsack, improving the previous $O(n+\min\{ w_\mathrm{ max}^3,p_\mathrm{ max}^3\})$ [Polak, Rohwedder and Wegrzyck, ICALP'21].
Categories: cs.DS