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 w max and the number of items n. A conditional lower bound rules out that Knapsack can be solved in time Oppn `wmax q 2´δ q for any δ ą 0 [Cygan, Mucha, Wegrzycki, Wlodarczyk'17, Künnemann, Paturi, Schneider'17]. This raised the question whether Knapsack can be solved in time r

Oppn wmax q 2 q. 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 r Opn 3 w 2 max q [Tamir'09], r Opn 2 w 2 max q and r Opnw 3 max q [Bateni, Hajiaghayi, Seddighin, Stein'18], Opn 2 w 2 max q and r Opnw 2 max q [Eisenbrand and Weismantel'18], Opn w3 max q [Polak, Rohwedder, Wegrzycki'21], and very recently r Opn `w125 max q [Chen, Lian, Mao, Zhang'23].

In this paper we resolve this question by designing an algorithm for Bounded Knapsack with running time r Opn `w2 max q, which is conditionally near-optimal. This resolves the question both for the classic 0-1-Knapsack problem and for the Bounded Knapsack problem.