Knapsack with Small Items in Near-Quadratic Time

The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research worked towards understanding the complexity of pseudopolynomial-time algorithms for Knapsack parameterized by the maximum item weight wmax and the number of items n. A conditional lower bound rules out that Knapsack can be solved in time O((n+wmax)2−δ) for any δ > 0 Cygan, Mucha, Wegrzycki, Wlodarczyk'17, Künnemann, Paturi, Schneider'17. This raised the question whether Knapsack can be solved in time Õ((n+wmax)2). This was open both for 0-1-Knapsack (where each item can be picked at most once) and Bounded Knapsack (where each item comes with a multiplicity). The quest of resolving this question lead to algorithms that solve Bounded Knapsack in time Õ(n3 wmax2) Tamir'09, Õ(n2 wmax2) and Õ(n wmax3) Bateni, Hajiaghayi, Seddighin, Stein'18, O(n2 wmax2) and Õ(n wmax2) Eisenbrand and Weismantel'18, O(n + wmax3) Polak, Rohwedder, Wegrzycki'21, and very recently Õ(n + wmax12/5) Chen, Lian, Mao, Zhang'23. In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time Õ(n + wmax2), which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.