Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing

We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time O (n + tp_), where n is the number of items, t is the knapsack capacity, and p_ is the maximum item profit. This improves over the O (n + t \, p_) -time algorithm based on the convolution and prediction technique by Bateni et al. ~ (STOC 2018). Moreover, we give some evidence, based on a strengthening of the Min-Plus Convolution Hypothesis, that our running time might be optimal. Our algorithm uses two new technical tools, which might be of independent interest. First, we generalize the O (n^1. 5) -time algorithm for bounded monotone min-plus convolution by Chi et al. ~ (STOC 2022) to the rectangular case where the range of entries can be different from the sequence length. Second, we give a reduction from general knapsack instances to balanced instances, where all items have nearly the same profit-to-weight ratio, up to a constant factor. Using these techniques, we can also obtain algorithms that run in time O (n + OPTw_), O (n + (nw_p_) ^1/3t^2/3), and O (n + (nw_p_) ^1/3 OPT^2/3), where OPT is the optimal total profit and w_ is the maximum item weight.