Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
<|reference_start|>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 $\widetilde{O}(n + t\sqrt{p_{\max}})$, where $n$ is the number of items, $t$ is the knapsack capacity, and $p_{\max}$ is the maximum item profit. This improves over the $\widetilde{O}(n + t \, p_{\max})$-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 $\widetilde{O}(n^{1.5})$-time algorithm for bounded monotone min-plus convolution by Chi et al.~(STOC 2022) to the \emph{rectangular} case where the range of entries can be different from the sequence length. Second, we give a reduction from general knapsack instances to \emph{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 $\widetilde{O}(n + OPT\sqrt{w_{\max}})$, $\widetilde{O}(n + (nw_{\max}p_{\max})^{1/3}t^{2/3})$, and $\widetilde{O}(n + (nw_{\max}p_{\max})^{1/3} OPT^{2/3})$, where $OPT$ is the optimal total profit and $w_{\max}$ is the maximum item weight.<|reference_end|>
@article{bringmann2024even,
    title={Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and
  Balancing},
    author={Karl Bringmann, Anita D"urr, Adam Polak},
    journal={arXiv preprint arXiv:2404.05681},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.05681},
    primaryClass={cs.DS}
}