Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
Abstract
We investigate pseudopolynomial-time algorithms for Bounded Knapsack and Bounded Subset Sum. Recent years have seen a growing interest in settling their fine-grained complexity with respect to various parameters. For Bounded Knapsack, the number of items n and the maximum item weight wmax are two of the most natural parameters that have been studied extensively in the literature. The previous best running time in terms of n and wmax is [Polak, Rohwedder, Węgrzycki ‘21]. There is a conditional lower bound of (n + wmax)2-o(1) based on (min, +)-convolution hypothesis [Cygan, Mucha, Węgrzycki, Włodarczyk ‘17]. We narrow the gap significantly by proposing an -time algorithm. Our algorithm works for both 0-1 Knapsack and Bounded Knapsack. Note that in the regime where wmax ≈ n, our algorithm runs in Õ(n12/5) time, while all the previous algorithms require Ω(n3) time in the worst case.