Knapsack with Small Items in Near-Quadratic Time

View PDF HTML (experimental)

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 O~((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 O~(n3w2max) [Tamir'09], O~(n2w2max) and O~(nw3max) [Bateni, Hajiaghayi, Seddighin, Stein'18], O(n2w2max) and O~(nw2max) [Eisenbrand and Weismantel'18], O(n+w3max) [Polak, Rohwedder, Wegrzycki'21], and very recently O~(n+w12/5max) [Chen, Lian, Mao, Zhang'23].
In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time O~(n+w2max), which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.