Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution

We revisit the classic 0-1-Knapsack problem, in which we are given $n$ items with their weights and profits as well as a weight budget $W$, and the goal is to find a subset of items of total weight at most $W$ that maximizes the total profit. We study pseudopolynomial-time algorithms parameterized by the largest profit of any item $p_{\max }$, and the largest weight of any item $w_{\max }$. Our main result are algorithms for 0-1-Knapsack running in time \tilde{O}(n\,w_\max\,p_\max^{2/3}) and \tilde{O}(n\,p_\max\,w_\max^{2/3}), improving upon an algorithm in time O(n\,p_\max\,w_\max) by Pisinger [J. Algorithms '99]. In the regime p_\max \approx w_\max \approx n (and $W\approx \mathrm{O}\mathrm{P}\mathrm{T}\approx n^2$) our algorithms are the first to break the cubic barrier $n^3$. To obtain our result, we give an efficient algorithm to compute the min-plus convolution of near-convex functions. More precisely, we say that a function $f\text{\hspace{0.17em}⁣}:[n]\mapsto \mathbf{Z}$ is $\mathrm{\Delta }$-near convex with $\mathrm{\Delta }\ge 1$, if there is a convex function $\breve{f}$ such that $\breve{f}(i)\le f(i)\le \breve{f}(i)+\mathrm{\Delta }$ for every $i$. We design an algorithm computing the min-plus convolution of two $\mathrm{\Delta }$-near convex functions in time $\tilde{O}(n\mathrm{\Delta })$. This tool can replace the usage of the prediction technique of Bateni, Hajiaghayi, Seddighin and Stein [STOC '18] in all applications we are aware of, and we believe it has wider applicability.