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.