Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
share
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 w_max 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 w_max is O(n + w^3_max) [Polak, Rohwedder, Wegrzycki '21]. There is a conditional lower bound of O((n + w_max)^2-o(1)) based on (min,+)-convolution hypothesis [Cygan, Mucha, Wegrzycki, Wlodarczyk '17]. We narrow the gap significantly by proposing a Õ(n + w^12/5_max)-time algorithm. Note that in the regime where w_max≈ n, our algorithm runs in Õ(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 Õ(nw_max) and Õ(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 w_max) for Bounded Subset Sum is Õ(n + w^5/3_max) [Polak, Rohwedder, Wegrzycki '21] and Õ(n + μ_max^1/2w_max^3/2) [implied by Bringmann '19 and Bringmann, Wellnitz '21], where μ_max refers to the maximum multiplicity of item weights.
READ FULL TEXT