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

arXiv: https://arxiv.org/abs/2305.01593 · HTML: https://mlsanity.com/paper/2305.01593/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2023.

## Built on by (most cited first, 1 of 1)

- [Tropical Attention: Neural Algorithmic Reasoning for Combinatorial Algorithms](https://mlsanity.com/paper/2505.17190/) (2025)

## Abstract (arXiv)

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.