Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results

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 O(n + w 3 max ) [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 O(n + w 12/5 max )-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 O(n 12/5 ) time, while all the previous algorithms require Ω(n 3 ) time in the worst case.

For Bounded Subset Sum, we give two algorithms running in O(nwmax) and O(n+w 3/2 max) time, respectively. These results match the currently best running time for 0-1 Subset Sum. Prior to our work, the best running times (in terms of n and wmax) for Bounded Subset Sum are O(n + w 5/3 max) [Polak, Rohwedder, Węgrzycki '21] and O(n + µ 1/2 maxw 3/2 max) [implied by Bringmann '19 and Bringmann, Wellnitz '21], where µmax refers to the maximum multiplicity of item weights.