Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

- An exact O~(n + (pₘₐₓ + wₘₐₓ)^1.5)-time algorithm, where pₘₐₓ and wₘₐₓ are the maximum profit and maximum weight of the items, respectively.

- An approximation scheme which runs in time O~(n + (1/ε)^1.5) by allowing resource augmentation (i.e. we approximate the optimal profit but we are also allowed to overshoot the capacity constraint W).

For these two settings the previously known results had matching conditional lower bounds. We avoid these lower bounds in the approximation setting by allowing resource augmentation, and in the exact setting by analyzing the time complexity in terms of weight and profit parameters (instead of only weight or only profit parameters).

Joint work with Karl Bringmann. The paper will appear in ICALP '22 and can be found in https://arxiv.org/abs/2205.08493