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 pmax, and the largest weight of any item wmax. Our main result are algorithms for 0-1-Knapsack running in time tildeO(n,w_max,p_max2/3) and tildeO(n,p_max,w_max2/3), improving upon an algorithm in time O(n,p_max,w_max) by Pisinger [J. Algorithms '99]. In the regime p_max ≈ w_max ≈ n (and W ≈ OPT ≈ n2) our algorithms are the first to break the cubic barrier n3. 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 colon [n] mapsto Z is Delta-near convex with Delta ≥ 1, if there is a convex function brevef such that brevef(i) ≤ f(i) ≤ brevef(i) + Delta for every i. We design an algorithm computing the min-plus convolution of two Delta-near convex functions in time tildeO(nDelta). 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.