Simple and Faster Algorithms for Knapsack

Abstract

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

References in corpus (4)

• Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution
• 0-1 Knapsack in Nearly Quadratic Time
• Knapsack and Subset Sum with Small Items
• Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results