Simple and Faster Algorithms for Knapsack
share
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 O(n^3/2·min{w_max,p_max})-time randomized algorithm for 0-1 knapsack, improving the previous 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 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].
READ FULL TEXT